Merge Intervals
Medium · rating 1500 · Intervals, Sorting
The first line has n. Each of the next n lines has two integers l r (an interval [l, r]). Print the merged, non-overlapping intervals in increasing order, one l r per line. Touching intervals (e.g. [1,3] and [3,5]) merge.
Constraints: 1 ≤ n ≤ 105
Editorial
Approach
Sort the intervals by start. Walk through them keeping the current merged interval; if the next one starts at or before the current end, extend the end to the max of the two — otherwise the current interval is finished and the next one begins a new block.
Why sorting is enough
Once sorted by start, any interval that overlaps a later one must overlap the running block, so a single left-to-right sweep captures every merge.
for l, r in sorted(intervals):
if out and l <= out[-1][1]:
out[-1][1] = max(out[-1][1], r)
else:
out.append([l, r])Complexity
Time: O(n log n) for the sort. Space: O(n).
Related problems
- Patrol Coverage — Medium
- Count Inversions — Medium
- Tournament Champion — Medium
- Count Anagram Groups — Medium
- Double-Booked? — Medium
- Fit the Most Tasks — Medium