Merge Intervals — InterviewPrepKit

Solving tips

Sort by start so every interval that should merge arrives consecutively, then sweep once maintaining a current block; O(n log n) time, O(n) space.
Extend the block when start <= last_end, and set the block's end to max(last_end, end) not just end, or a nested interval like [2,3] inside [1,10] wrongly shrinks it.
These are closed intervals, so touching intervals like [1,4] and [4,5] must merge: use '<=' in the reach test.
Sort by START specifically (not end or descending); the 'only neighbors matter' invariant depends on ascending starts.

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 be careful — why is it not just "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

class Solution:
    def merge(self, 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 hopeless next 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 — nothing after it can reach back, because all later starts are even bigger.

from typing import List

class Solution:
    def merge(self, 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 coordinates were huge streams of events rather than a small list, the same result falls out of 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 strictly 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.