Merge overlapping intervals

TL;DR: Sort by start, then sweep once: each interval either extends the last merged one (when its start is at or before the last end) via max of the ends, or starts a new group.

How to approach it Intervals questions are Palantir screen staples because they model real deployment data: shift schedules, sensor windows, booking spans. The universal first move: sort by start. After sorting, overlap detection becomes purely local: each interval either extends the last merged one or starts a new one. Clarify the boundary semantics before coding: do [1, 4] and [4, 5] overlap? (Convention: yes for closed intervals; confirm it.)

Sorted, the two overlapping inputs collapse into one bar and the separate one is left alone:

A strong answer

def merge_intervals(intervals: list[list[int]]) -> list[list[int]]:
    if not intervals:
        return []
    intervals.sort(key=lambda iv: iv[0])
    merged = [list(intervals[0])]
    for start, end in intervals[1:]:
        last = merged[-1]
        if start <= last[1]:                  # overlaps (or touches) the last merged
            last[1] = max(last[1], end)       # max matters: [1,10] then [2,3]
        else:
            merged.append([start, end])
    return merged

Narrate the two details an interviewer is waiting for: start <= last[1] implements the touching-intervals decision you clarified, and max(last[1], end) handles contained intervals: [1, 10], [2, 3] must stay [1, 10], and skipping the max is the classic bug. O(n log n) from the sort, O(n) output.

The sweep traced on the standard input (produced by running the code), so the "purely local" claim is visible:

Each interval looks at exactly one thing, the end of the last merged group, which is the property sorting bought you: after the sort, anything that could overlap [2,6] is adjacent to it. Worth saying in the FDE framing: the merged list's complement is usually the deliverable at a customer site. Merge the on-call shifts and the gaps between merged groups ([6,8] and [10,15] here) are the uncovered hours; merge the sensor windows and the gaps are the blind spots. That is a two-line follow-up once merge_intervals exists, and interviewers often walk the question exactly there.

Tests covering the traps:

assert merge_intervals([[1, 3], [2, 6], [8, 10], [15, 18]]) == [[1, 6], [8, 10], [15, 18]]
assert merge_intervals([[1, 4], [4, 5]]) == [[1, 5]]    # touching
assert merge_intervals([[1, 10], [2, 3]]) == [[1, 10]]  # containment
assert merge_intervals([[5, 6], [1, 2]]) == [[1, 2], [5, 6]]  # unsorted input
assert merge_intervals([]) == []
assert merge_intervals([[1, 1]]) == [[1, 1]]            # zero-length

What interviewers probe next (1) Insert one interval into an already-merged list, the natural follow-up (and the next question in this track): you can answer "merge again in O(n log n)" but the O(n) three-phase scan is what they want. (2) Total covered time? Sum end - start over the merged output, one line once you have merge_intervals. (3) Intervals arrive as a stream? Keep a sorted structure (e.g., sortedcontainers or a balanced-tree discussion) and merge neighbors on insert: say the data-structure name, sketch the cost, don't implement unless asked. (4) Max simultaneous overlaps? That's the sweep-line/flight-segments problem, a different technique (sort the +1/-1 events), and recognizing it's different is the point.

Common mistakes Forgetting to sort, or sorting by end. Missing the containment case by writing last[1] = end. Getting the touching-boundary semantics wrong silently instead of asking: interviewers explicitly note whether you clarified [1,4]/[4,5]. Mutating the caller's input without mentioning it (the sort in place is fine, but say you're doing it and would copy in production code). And over-engineering: this is a warm-up; a clean 12-line solution with tests in 8 minutes beats a class hierarchy in 25.