Given a collection of intervals where each interval is a pair [start, end], merge all overlapping intervals and return the result sorted by start time.
Two intervals overlap if one starts before or when the other ends — that is, intervals [a, b] and [c, d] overlap when a ≤ d and c ≤ b. Touching intervals (e.g. [1, 2] and [2, 3]) are considered overlapping and must be merged.
Line 1: an integer n, the number of intervals.
Lines 2 to n+1: two space-separated integers start end per line.
One merged interval per line as start end, sorted by ascending start.
Example 1
Input
4 1 3 2 6 8 10 15 18
Expected
1 6 8 10 15 18
Explanation
[1,3] and [2,6] overlap and merge into [1,6]. [8,10] and [15,18] are disjoint and pass through unchanged.
Example 2
Input
3 1 4 2 5 3 6
Expected
1 6
Explanation
All three intervals overlap in a chain — [1,4] overlaps [2,5] which overlaps [3,6] — so the entire range merges into a single [1,6].
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →