Maximum Compatible Meetings

Difficulty: 1500 3000 ms 128 MB

greedy intervals

Choose as many intervals as possible so that no two chosen intervals share any point (endpoints inclusive). Print the maximum count.

Input: the first line has N; the next N lines each have two integers a b (a ≤ b).

Output: the maximum number of pairwise disjoint intervals.

Constraints:

• 1 ≤ N ≤ 10⁵
• 0 ≤ a ≤ b ≤ 10⁶

Sample Tests

4
1 3
2 4
3 5
6 7

2

2
1 5
2 3

1

Read the Editorial