DSAMotivator

Merge Intervals

Medium·📏 Intervals·Open on LeetCode ↗

Given a collection of ranges, combine every group that touches or overlaps into a single range and return what's left.

intervals = [[8,10], [1,3], [15,18], [2,6], [9,12]]step 1/13
8–10
1–3
15–18
2–6
9–12
0
1
2
3
4

Unsorted, any pair might overlap — so the first move is to sort by start time.

1def merge(intervals):
2    intervals.sort(key=lambda x: x[0])
3    out = []
4    for start, end in intervals:
5        if out and start <= out[-1][1]:
6            out[-1][1] = max(out[-1][1], end)
7        else:
8            out.append([start, end])
9    return out
Read the 13 steps as text
  1. 1Unsorted, any pair might overlap — so the first move is to sort by start time.
  2. 2Now every interval that could overlap the current one has already been seen.
  3. 3Take 1–3.
  4. 4Nothing open reaches 1. 1–3 starts a new range.
  5. 5Take 2–6.
  6. 62 is not past 3, so they touch — 1–3 becomes 1–6.
  7. 7Take 8–10.
  8. 8Nothing open reaches 8. 8–10 starts a new range.
  9. 9Take 9–12.
  10. 109 is not past 10, so they touch — 8–10 becomes 8–12.
  11. 11Take 15–18.
  12. 12Nothing open reaches 15. 15–18 starts a new range.
  13. 135 ranges collapsed into 3: 1–6, 8–12, 15–18.

The idea

In arbitrary order, an interval can overlap anything — so deciding whether to merge means comparing against everything. That's the O(n²) trap.

Sorting by start time destroys that possibility, and it's worth being precise about why. Once starts are in order, any interval that could overlap the current one must have started earlier, and among those only the most recent output range can still be open. Every earlier one ended before it.

So the comparison shrinks from "all of them" to "the last one I emitted". Overlap is then a single test: does the new interval start at or before the last one ends?

When they do overlap, the merged range keeps the earlier start automatically — sorting guaranteed it — and takes the later of the two ends. That `max` is the part people drop, and it's needed whenever one interval is entirely swallowed by another.

The approach

  1. 1Sort the intervals by start.
  2. 2Walk through them, keeping a list of merged output.
  3. 3If the current interval starts at or before the end of the last output interval, they touch — extend that interval's end to the larger of the two.
  4. 4Otherwise there's a genuine gap, so append the current interval as a new one.

Complexity

Time
O(n log n)
Space
O(n)

The sort dominates; the merge pass itself is linear. The space is the output, or O(log n) of sort overhead if you're allowed to merge in place.

Code

def merge(intervals):
    intervals.sort(key=lambda x: x[0])
    out = []
    for start, end in intervals:
        if out and start <= out[-1][1]:
            out[-1][1] = max(out[-1][1], end)
        else:
            out.append([start, end])
    return out

What goes wrong

  • •Writing `out[-1][1] = end` instead of taking the max. An interval fully contained inside the previous one then shrinks it, silently losing coverage.
  • •Using `<` rather than `<=` for the overlap test. Ranges that merely touch at a boundary are almost always meant to merge; check which the problem wants and say so.
  • •Sorting by end time. It's the right sort for the maximum-non-overlapping-intervals problem and the wrong one here.