Course Content

Merge Intervals

This is the most asked interval question, and the template it teaches is the base of most others. It looks easy, and it is — but one line is wrong in a large share of first attempts, and the usual tests don't catch it.

Sorted by start, anything that overlaps must overlap the interval still open — one is enough.

The problem

Given a list of intervals [start, end] in any order, merge every group of overlapping intervals into one, and return the resulting intervals. Intervals that touch at one point, such as [1, 4] and [4, 5], count as overlapping.

[[8, 10], [1, 3], [15, 18], [2, 6]] → [[1, 6], [8, 10], [15, 18]]. [1, 3] and [2, 6] overlap; the others stand alone.
[[1, 4], [4, 5]] → [[1, 5]]. They touch at 4, so they merge.

Constraints: 1 ≤ n ≤ 10⁴, 0 ≤ start ≤ end ≤ 10⁴.

Clarifying questions

Do touching intervals merge? Yes, [1, 4] and [4, 5] become [1, 5].
Is the input sorted? No.
Does the output need an order? Returning it sorted by start is natural and usually expected.
May I change the input? Assume no; work on a sorted copy.

Approach 1: merge any overlapping pair, then start again

Without order, the only way is to search for any pair that overlaps, merge it, and repeat — because the merged interval may now overlap something you already checked.

Python

1from itertools import combinations23def merge_brute(intervals: list[list[int]]) -> list[list[int]]:4    """Merge any overlapping pair, then start the search again."""5    merged = [list(i) for i in intervals]6    changed = True7    while changed:8        changed = False9        for i, j in combinations(range(len(merged)), 2):10            a, b = merged[i], merged[j]11            if a[0] <= b[1] and b[0] <= a[1]:12                merged[i] = [min(a[0], b[0]), max(a[1], b[1])]13                del merged[j]14                changed = True15                break                            # the list changed: rescan16    return sorted(merged)

Each search over pairs is O(n²), and there can be up to n - 1 merges, each followed by a new search. That is O(n³) in the worst case. At n = 10⁴ it is hopeless, and the restart-after-change logic is the kind of code that hides bugs.

The key insight

Sort by start. Now think of walking along the number line from left to right, holding one open interval — the merged interval you are currently building.

The next interval in sorted order starts at or after the open interval's start. Either it starts at or before the open interval's end — then they overlap, and the open interval grows — or it starts after the end, and there is a gap. A gap is final: every later interval starts even further right, so nothing can ever bridge back to the open interval. You close it and open a new one.

So you never look back further than the open interval. Every earlier interval that could overlap the current one has already been folded into it. That one sentence is the proof, and it is worth saying in the interview.

The one subtle part is the new end. The next interval might sit completely inside the open one: [1, 10] then [3, 5]. The merged end must stay 10, so it is max(open end, new end), never just the new end.

Why sort by start and not by end? Because the argument needs "every later interval starts further right". Sorted by end, a long interval that starts early can come last. On [[2, 3], [4, 5], [1, 10]] the same loop, sorted by end, returns [[2, 3], [4, 10]]: it never goes back to fold [2, 3] in, and it loses the point 1. The right answer is [[1, 10]].

Approach 2: sort, then sweep with one open interval

Python

1def merge(intervals: list[list[int]]) -> list[list[int]]:2    """Sort by start, then extend or close one open interval."""3    merged: list[list[int]] = []4    for start, end in sorted(intervals, key=lambda i: i[0]):5        if merged and start <= merged[-1][1]:    # overlaps the open interval6            merged[-1][1] = max(merged[-1][1], end)7        else:                                    # a gap: open a new interval8            merged.append([start, end])9    return merged

Dry run on [[8, 10], [1, 3], [15, 18], [2, 6]]. Sorted by start: [1, 3], [2, 6], [8, 10], [15, 18].

Current	Open interval	`start <= open end`?	Action	Result so far
`[1, 3]`	—	—	open `[1, 3]`	`[[1, 3]]`
`[2, 6]`	`[1, 3]`	`2 <= 3` — yes	end = `max(3, 6)` = 6	`[[1, 6]]`
`[8, 10]`	`[1, 6]`	`8 <= 6` — no	open `[8, 10]`	`[[1, 6], [8, 10]]`
`[15, 18]`	`[8, 10]`	`15 <= 10` — no	open `[15, 18]`	`[[1, 6], [8, 10], [15, 18]]`

And the containment case, [[1, 10], [3, 5]]:

Current	Open interval	`start <= open end`?	New end	Result
`[3, 5]`	`[1, 10]`	`3 <= 10` — yes	`max(10, 5)` = 10	`[[1, 10]]`

With end in place of the max, the result would be [[1, 5]] — wrong, and quietly so.

Complexity. Sorting is O(n log n); the sweep is O(n). Total O(n log n) time. Space O(n) for the output and the sorted copy. The new intervals are created with [start, end], so updating merged[-1][1] never changes the caller's lists.

Edge cases

One interval: it is opened and returned.
Touching, [[1, 4], [4, 5]]: 4 <= 4, so they merge into [1, 5]. For "touching does not merge", change <= to <.
Containment, container first, [[1, 10], [3, 5]]: the max keeps the end at 10.
Everything overlaps, such as [[1, 4], [2, 5], [3, 6]]: one open interval grows to [1, 6].
Zero-length intervals, [4, 4]: allowed by the constraints, and handled like any other.

Follow-ups

"The input is already sorted by start." Skip the sort: O(n) time.
"Return the total length covered by the intervals." Merge, then sum end - start over the result. Merging first stops overlapping parts from being counted twice.
"Intervals arrive one at a time, and you must report the merged set at any moment" (Data Stream as Disjoint Intervals). Keep the merged intervals in a sorted structure keyed by start; each new interval merges with at most its neighbours, found by binary search.