Merge Intervals

mediumArrays & Hashing+20 XPTime limit 2s

Merge all overlapping intervals and print the result in increasing order of start. Intervals that touch (like [1,4] and [4,5]) also merge.

Input:

line 1: n
next n lines: start end (start ≤ end)

Output: the merged intervals, one start end per line, sorted by start.

Constraints: 1 ≤ n ≤ 10⁵, 0 ≤ start ≤ end ≤ 10⁹.

Sample input 1

Sample output 1

1 6
8 10
15 18

Sample input 2

2
1 4
4 5

Sample output 2

1 5

📖 Stuck? Learn the pattern

Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).

Loading editor…