Merged Timeline

Difficulty: 1400 3500 ms 128 MB

intervals sorting

Merge all overlapping or touching intervals and print the resulting disjoint intervals in increasing order.

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

Output: the merged intervals, one per line.

Constraints:

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

Sample Tests

3
1 3
2 5
7 8

1 5
7 8

1
4 4

4 4

Read the Editorial