Merge Intervals — InterviewPrepKit

Problem

You are given a list of closed intervals [start, end] in no particular order. Whenever two intervals overlap — including merely touching at an endpoint, since the intervals are closed — they should be fused into a single interval covering both. Return the list of merged intervals: the smallest set of pairwise non-overlapping intervals that covers exactly the same points as the input. Output order should be by start time.

Examples

intervals = [[1,3],[2,6],[8,10],[15,18]] → [[1,6],[8,10],[15,18]] — [1,3] and [2,6] overlap and fuse into [1,6].
intervals = [[1,4],[4,5]] → [[1,5]] — closed intervals sharing the point 4 count as overlapping.
intervals = [[1,4],[0,2],[3,5]] → [[0,5]] — a chain of overlaps collapses into one interval.

Constraints

1 <= len(intervals) <= 10^4
0 <= start <= end <= 10^4

10^4 intervals: repeated pairwise merging (O(n^2)) is the naive path; O(n log n) via sorting is the expected answer.

Think about it first

Hint 1

In the raw input, an interval's merge partners can be anywhere in the list. What preprocessing step guarantees that everything an interval merges with sits right next to it?

Hint 2

After sorting by start, suppose you're building the output left to right and the next interval starts before or at the end of the last interval you've built. What single update handles it, and why is it not simply "extend the end"?

Hint 3

Sort by start. Keep the output's last interval as the "current block": if the next interval's start is ≤ the block's end, set the block's end to the max of the two ends (the next interval might be nested inside); otherwise start a new block.

TL;DR

Sort by start, sweep once, extending or starting a block — O(n log n) time, O(n) space for the output.

Approach 1 — Brute force: merge pairs until nothing changes

Scan for any overlapping pair, fuse it, and restart. Repeat until a full scan finds no overlap. Closed intervals [a, b] and [c, d] overlap when a <= d and c <= b.

from typing import List

def merge(intervals: List[List[int]]) -> List[List[int]]:
    items = [list(it) for it in intervals]
    changed = True
    while changed:
        changed = False
        out: List[List[int]] = []
        for a, b in items:
            merged_in = False
            for block in out:
                if a <= block[1] and block[0] <= b:
                    block[0] = min(block[0], a)
                    block[1] = max(block[1], b)
                    merged_in = True
                    changed = changed or True
                    break
            if not merged_in:
                out.append([a, b])
        if len(out) == len(items):
            changed = False
        items = out
    return sorted(items, key=lambda it: it[0])

Complexity: each pass is O(n^2) and a pass can trigger another (merging two blocks may make a third overlap the result), so worst case is O(n^2) per round with up to O(n) rounds — O(n^3) in pathological chains. Space O(n).

At n = 10^4, quadratic-or-worse repeated scanning is far too slow compared to a single sort.

Approach 2 — Sort + linear sweep

The insight: sorted by start, every interval that should merge into the current block arrives consecutively. While the incoming interval starts at or before the block’s end, it belongs to the block; the moment one starts later, the block is final, since every later interval starts further right and cannot extend it.

from typing import List

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

Walkthrough on [[1,3],[2,6],[8,10],[15,18]]:

Sort by start → unchanged.
[1,3]: output empty → new block. merged = [[1,3]].
[2,6]: 2 <= 3 → extend: end becomes max(3, 6) = 6. merged = [[1,6]].
[8,10]: 8 <= 6 is false → new block. merged = [[1,6],[8,10]].
[15,18]: 15 <= 10 is false → new block. merged = [[1,6],[8,10],[15,18]]. Matches the expected output.

And the nesting case [[1,10],[2,3]]: [2,3] has 2 <= 10 → end becomes max(10, 3) = 10 — the max keeps the block from shrinking.

Complexity: O(n log n) time (the sort dominates the O(n) sweep), O(n) space for the output (sorting in place otherwise).

Variant worth knowing: if the input were a large stream of events rather than a small list, the same result comes from a sweep line over +1/-1 events at starts and ends: the merged intervals are the maximal stretches where the running count is positive. For this problem the sort-and-sweep above is simpler.

Common pitfalls

Writing the extend as merged[-1][1] = end instead of max(...) — a nested interval like [2,3] inside [1,10] would wrongly shrink the block.
Using start < merged[-1][1] — closed intervals that touch, like [1,4] and [4,5], must merge, so the test is <=.
Forgetting to sort first and sweeping the raw input — the “only neighbors matter” property exists only after sorting by start.
Sorting by end (or by start descending) out of habit from other interval problems — the sweep’s invariant depends specifically on ascending starts.

Pattern takeaway

Sort by start, then maintain one growing “current block” and ask a single question per interval: does it reach the block (start <= block_end) or not? Extend with max of ends, or seal the block and start fresh. This sort-and-sweep with a max-extend is the backbone that Insert Interval, Meeting Rooms, and most other interval problems specialize.