Merge Overlapping Intervals

Problem

Given n meeting time intervals, merge any overlapping ones and print the result in ascending order. The classic calendar-app interview problem.

Input

Line 1: n. Next n lines: `start end`.

Output

Merged intervals, one per line as `start end`.

Constraints

1 ≤ n ≤ 10^5

Sample input

Sample output

1 6
8 10
15 18

Explanation

[1,3] and [2,6] overlap → merge to [1,6]. The rest are disjoint.

intervalssortinggreedy@Google@Meta@Bloomberg

Visible test cases

out: 1 6
8 10
15 18

Your solution — run it, use AI if stuck

cpp