LeetCode 56 · Intervals

Merge Intervals, explained with a picture

Merging overlapping meetings into blocks.

MediumIntervals
▶ Watch it step by step

The problem

Merge all overlapping intervals and return the non-overlapping result.

Input:  [1,3] [2,6] [8,10] [15,18]
Output: [1,6] [8,10] [15,18]

Picture it

Picture meetings on a calendar. Sort them by start time. Walk through them: if a meeting starts before the current busy block ends, it stretches the block; otherwise the block is finished and the meeting starts a new one.

How to recognise it

  • The input is a set of intervals in any order, and overlapping ones must be combined into single blocks.
  • Two intervals overlap when one starts before (or exactly when) the other ends. Here touching counts: [1, 4] and [4, 5] merge into [1, 5].
  • Once the intervals are sorted by start, every interval that can join the current block comes right after it. You never need to look back further than the last block.
  • Up to 10^4 intervals, so comparing every pair repeatedly is too slow, but sorting (O(n log n)) is fine.
  • "Sort by start, then sweep" is the first move for most interval problems.

Start with brute force

Look for any two intervals that overlap, replace them with their union, and start the search again. Stop when no pair overlaps.

def merge_brute(intervals):
    items = [list(iv) for iv in intervals]
    merged = True
    while merged:
        merged = False
        for i in range(len(items)):
            for j in range(i + 1, len(items)):
                a, b = items[i], items[j]
                if a[0] <= b[1] and b[0] <= a[1]:      # they overlap
                    items[i] = [min(a[0], b[0]), max(a[1], b[1])]
                    items.pop(j)
                    merged = True
                    break
            if merged:
                break
    return sorted(items)

Finding one overlapping pair can take O(n²) checks, and there can be up to n − 1 merges, so the worst case is O(n³). For n = 10^4 that is on the order of 10^12 steps. Space is O(n) for the copy.

From brute force to the idea

  1. Find the waste. The brute force compares intervals that are far apart in time and can never overlap, and it restarts after every merge.
  2. Sort by start. intervals.sort() sorts the pairs by start (and by end when starts tie). Now any interval that overlaps the current block must start before that block ends, and it appears right after the intervals already in the block.
  3. Keep a running block. out[-1] is the block being built. It starts as the first interval.
  4. Extend or start fresh. For each next interval, if start <= out[-1][1] it overlaps (or touches), so stretch the block's end to max(out[-1][1], end). The max matters: a short interval inside a long one must not shrink it. Otherwise there is a gap, the block is finished, and [start, end] starts a new one.
  5. Only the last block can change. Every earlier block ended before the current block started, and later intervals start even later, so they can never reach back.

This is the key idea: sort by start, then one sweep that either extends the last block or opens a new one.

The key idea

Sort by start, then extend or start a new block. O(n log n).

Python solution

def merge(intervals):
    intervals.sort()
    out = [intervals[0]]
    for start, end in intervals[1:]:
        if start <= out[-1][1]:
            out[-1][1] = max(out[-1][1], end)   # overlaps: stretch the block
        else:
            out.append([start, end])            # gap: a new block
    return out

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.

Complexity

ApproachTimeSpace
Brute forceO(n³) worst case: up to n merges, each found by an O(n²) pair searchO(n): a copy of the intervals
Sort and sweep (shown code)O(n log n): the sort; the sweep is O(n)O(n): the output (and the sort's working memory)

Edge cases

  • One interval: the loop does not run and [[a, b]] is returned.
  • Touching ([[1, 4], [4, 5]]): 4 <= 4, so they merge into [[1, 5]].
  • Contained ([[1, 10], [2, 3]]): max keeps the end at 10, giving [[1, 10]].
  • Unsorted input ([[8, 10], [1, 3], [2, 6]]): sorting first gives [[1, 6], [8, 10]].
  • Empty list: LeetCode guarantees at least one interval. The shown code reads intervals[0] and raises IndexError on [].
  • The input is changed: sort() reorders the caller's list in place, and out[0] is the caller's own first interval, so stretching it edits the input too. Pass a copy if the caller still needs it.
  • Tuples: with [(1, 3), (2, 6)] the line out[-1][1] = ... raises TypeError, because tuples cannot be changed. The input must be lists.

Common mistakes

  • Forgetting to sort, so overlapping intervals that are not neighbours in the input stay separate.
  • Writing out[-1][1] = end instead of taking the max, which shrinks a block when a short interval sits inside a long one.
  • Using < instead of <=, so touching intervals like [1, 4] and [4, 5] are not merged.
  • Comparing each interval only with the previous input interval instead of the current merged block.
Your turn: total covered length

Return the total length of time covered by at least one interval, where [a, b] has length b − a. For [[1, 3], [2, 6], [8, 10]] the answer is 5 + 2 = 7. Describe your approach, then write it if you like.

Compare with our answer

Run the same sort and sweep, but instead of storing blocks, add each block's length to a total when it closes, and once more for the last block.

def covered_length(intervals):
    total = 0
    cur_start, cur_end = None, None
    for start, end in sorted(intervals):
        if cur_end is not None and start <= cur_end:
            cur_end = max(cur_end, end)
        else:
            if cur_end is not None:
                total += cur_end - cur_start
            cur_start, cur_end = start, end
    if cur_end is not None:
        total += cur_end - cur_start
    return total

Time O(n log n), space O(n) for the sorted copy. It also works on an empty list (returns 0).

A strong answer mentions: summing merged blocks rather than raw intervals (so overlaps are not counted twice), adding the final block after the loop, and the max for contained intervals.

Check what stuck

1. A firewall holds 10^4 IP address ranges, some overlapping. You must collapse them into the fewest non-overlapping ranges. Which approach fits best?

2. After sorting, why is it enough to compare each interval with the last merged block only?

3. A learner writes out[-1][1] = end instead of using max. Which input now gives a wrong answer?

Score 60% or more and the lesson is marked complete.