The seminar hall is booked back-to-back all day, and Mitu (moonlighting as room coordinator) must pick the MAXIMUM number of non-overlapping sessions that can be scheduled in one hall. Given N activities each with a start and end time, print the MAXIMUM number of non-overlapping activities you can attend (an activity ending at time t and another starting at time t may both be attended).
Input
Line1: N. Next N lines: start end.
Output
Maximum number of activities.
Constraints
1 ≤ N ≤ 10^5
Sample Input
4 1 3 2 4 3 5 0 6
Sample Output
2
main.c
Loading editor…
Write C, then Run (custom I/O) or Submit (sample tests). ⌘/Ctrl+Enter submits.