Merge Intervals

Medium#56merge

You get a list of intervals [start, end] in any order. Join every group of intervals that overlap into one interval and return the intervals that are left. Intervals that only touch, like [1, 4] and [4, 5], also count as overlapping. Our example: [9, 12], [1, 4], [5, 7], [4, 5], [10, 11] — the answer is [1, 7], [9, 12].

56 Merge IntervalsWalkthrough · 1×

Example: [9, 12], [1, 4], [5, 7], [4, 5], [10, 11]. Each interval is a bar on the axis, sorted by start; the result row is at the bottom.

[1, 4][4, 5][5, 7][9, 12][10, 11]result0123456789101112
not looked at yetcurrent intervallast interval in the resultresultalready handled

Sort by start: [1, 4], [4, 5], [5, 7], [9, 12], [10, 11]

01/18
restart · back · play · step
Speed
1function merge(intervals):
2 sort intervals by start
3 result = []
4 for each [start, end] in intervals:
5 if result is empty or start > result.last.end:
6 add [start, end] to result
7 else:
8 result.last.end = max(result.last.end, end)
9 return result
state
result
–
start
–
end
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. After sorting by start, an interval that starts past the end of the last group is followed only by intervals that start even further right. None of them can reach back into the group, so each group comes in a row.
  2. So each interval is compared only with the last one in the result: if it starts no later than its end, it joins it; otherwise it opens a new group.
  3. The end becomes max of the two ends, not just the new end: [10, 11] lies inside [9, 12], and taking its end would cut the interval short.

Complexity

Time O(n log n): the sort; the pass after it is O(n). Memory O(n) for the result, plus what the sort needs.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.