Merged Interval Count

Difficulty: 1400 3000 ms 128 MB

intervals sorting

Merge all overlapping or touching intervals [a, b] and print how many disjoint blocks remain.

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

Output: the number of merged blocks.

Constraints:

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

Sample Tests

3
1 3
2 5
7 8

2

2
1 2
2 3

1

Read the Editorial