Merge Intervals

Interview Prep

StandardIntervalsarrayssortingintervals

The problem

Given a collection of closed intervals, return the minimal set of intervals that covers exactly the same set of points (i.e., merge all overlapping ranges). Output order is by start position.

Pattern: sort then sweep

Sort by start. Then walk left to right, maintaining a single "open" interval at the end of the output. For each new interval: if its start is ≤ the open interval's end, they touch or overlap — extend the open interval's end. Otherwise close the open one and start a new one with the incoming interval.

Sorting is the only non-linear step. Once sorted, every interval is inspected exactly once. Total: O(n log n).

Solution

def merge(intervals: list[list[int]]) -> list[list[int]]:
    if not intervals: return []
    intervals.sort(key=lambda iv: iv[0])     # sort by start
    out = [intervals[0][:]]                  # copy to avoid mutating input
    for s, e in intervals[1:]:
        if s <= out[-1][1]:
            out[-1][1] = max(out[-1][1], e)  # overlap -> extend the open interval
        else:
            out.append([s, e])
    return out

Trace

intervals = [[1,3], [2,6], [8,10], [15,18]]
sort:        [[1,3], [2,6], [8,10], [15,18]]   (already sorted)

out = [[1,3]]
(s,e)=(2,6): 2 <= 3, extend out[-1][1] = max(3,6) = 6.   out=[[1,6]]
(s,e)=(8,10): 8 > 6, append.                              out=[[1,6],[8,10]]
(s,e)=(15,18): 15 > 10, append.                           out=[[1,6],[8,10],[15,18]]

return [[1,6], [8,10], [15,18]]

Companion problem: Insert Interval

Given an already-sorted, non-overlapping list and a single new interval, insert it and merge as needed in O(n) — no sort required. The classic three-phase sweep: before, during, after. 

def insert(intervals: list[list[int]], new: list[int]) -> list[list[int]]:
    """Assume intervals is already sorted and non-overlapping."""
    out, ns, ne = [], new[0], new[1]
    i, n = 0, len(intervals)

    # 1) intervals entirely before new -> emit as-is
    while i < n and intervals[i][1] < ns:
        out.append(intervals[i]); i += 1

    # 2) overlapping with new -> absorb
    while i < n and intervals[i][0] <= ne:
        ns = min(ns, intervals[i][0])
        ne = max(ne, intervals[i][1])
        i += 1
    out.append([ns, ne])

    # 3) intervals entirely after new -> emit as-is
    while i < n:
        out.append(intervals[i]); i += 1
    return out

Complexity

Variations worth knowing