7. Activity Selection
MediumGreedySorting
Given n activities with start and end times, select the maximum number of activities that do not overlap. An activity may start at the same time another ends.
Input format
Line 1: n Next n lines: start end
Output format
The maximum number of non-overlapping activities.
Example 1
Input
6 1 2 3 4 0 6 5 7 8 9 5 9
Output
4
Example 2
Input
3 1 4 2 3 3 5
Output
2
Constraints
1 ≤ n ≤ 10⁵ 0 ≤ start < end ≤ 10⁹
Read input from standard input and print the answer to standard output. Your code is judged against 5 test cases, most of them hidden.
Loading the MyLoginn IDE…