Coding Interview: How Do You Merge Overlapping Intervals?

Prompt and Scope

Given an unsorted list of closed intervals intervals, where every item is [start, end] and start <= end, merge all overlaps. Return a new list that is sorted by start, is pairwise disjoint, and covers exactly the same points. This problem uses closed intervals, so [1, 4] and [4, 5] share the point 4 and must become [1, 5]. The function must not mutate its input.

For example:

Input:  [[8, 10], [1, 3], [2, 6], [15, 18]]
Output: [[1, 6], [8, 10], [15, 18]]

The input may be empty and may contain duplicate intervals, negative endpoints, zero-length intervals, or intervals fully contained inside others. The base problem guarantees two valid integer endpoints per item, so input-format validation is outside the merge function. This is a general software-engineering coding problem. Its core skill is turning arbitrary order into an order that permits local decisions, then proving that the greedy decision cannot miss a later connection.

What the Interviewer Evaluates

The first signal is whether the candidate defines interval semantics. Closed intervals, half-open intervals, and a rule that merges merely adjacent ranges can produce different conditions. Writing start < current_end without stating the contract can fail a shared-endpoint case.

The second signal is whether the candidate can explain why sorting helps. After sorting, the next start cannot be smaller than the current start. If it is already greater than the end of the current merged interval, every later start will be greater too, so the current interval is safe to emit. A strong answer gives this finalization argument instead of only saying “sort and scan.”

The third signal is handling containment. When [1, 10] meets [2, 3], the merged end must be max(10, 3). Overwriting it with 3 loses covered points. Chained overlaps must also be compared with the expanding merged interval, not just with the preceding raw input interval.

The interviewer will also inspect the mutation contract, complexity, and validation strategy. Sorting normally determines the O(n log n) running time. This implementation spends O(n) space on a sorted copy and result to keep the input unchanged. Tests should go beyond the standard example: assert that the input is unchanged, that output is ordered and disjoint, and that randomized results match a slow reference implementation.

Clarifying Questions Before Answering

• Are these closed or half-open intervals, and do shared endpoints merge? They are closed here, so the condition is nextstart <= currentend. If the product treats adjacency as separate, use a strict comparison. For [a, b), whether contiguous but non-overlapping ranges merge is a separate choice.
• Is the input already sorted by start? Sorted input needs only a linear scan, reducing time to O(n). Unsorted input requires sorting or a specialized method tied to a bounded endpoint domain.
• May I mutate the input? If yes, sort in place and compact with a write pointer. If no, copy the data or use a sorting operation that returns a new list.
• Are endpoints integers from a small bounded range? Comparison sorting is the direct choice for arbitrary comparable values. A small integer universe may allow buckets or a difference array, but its cost depends on the coordinate range rather than only on n.
• Is this one offline merge or a continuing stream? A stream ordered by start can be merged and emitted online. An arbitrary-order stream cannot safely finalize early because a future interval may start earlier and bridge existing components.
• Does output need only boundaries, or must it preserve interval metadata? Merging boundaries does not define how labels, permissions, or prices combine. Metadata needs an explicit aggregation rule.

30-Second Answer Framework

“I will first confirm that these are closed intervals, shared endpoints count as overlap, and I cannot mutate the input. I will copy and sort by start and end, then maintain one current merged interval. If the next start is at or before the current end, I extend the end to the maximum of the two ends. Otherwise no later interval can reach the current one, so I append it and start a new range. I append the last range after the scan. Sorting costs O(n log n), the scan costs O(n), and the sorted copy plus output use O(n) space. The correctness invariant is that emitted intervals are final and the current interval is exactly the last not-yet-emitted connected component.”

Step-by-Step Deep Dive

A direct approach repeatedly finds any overlapping pair, replaces it with its union, and restarts until nothing changes. It is easy to express with nested loops, but a newly merged interval may overlap something already examined, so it can require many passes and reach O(n²) or worse. That method is useful as a small-input test oracle, but it is a poor primary solution.

Sorting converts the global problem into a left-to-right scan. Sort by (start, end) ascending. Maintain current = [currentstart, currentend], the final merged component among processed intervals that has not yet been emitted. For each next [start, end]:

1. If start <= currentend, the two closed intervals overlap, so set currentend to max(current_end, end).
2. If start > current_end, there is a gap. Every later start is at least start, so no future interval can reach current. Emit it and begin a new current interval.

The scan maintains three invariants:

1. Emitted intervals are sorted, pairwise disjoint, and will never change.
2. The union of the emitted intervals and current equals the union of all processed input intervals.
3. current is the last maximal merged component among processed intervals and the only component that can overlap the next interval.

All three hold after initializing from the first sorted interval. An overlap only extends the right endpoint of the last component and preserves its union. At a gap, sorting guarantees that every future start lies beyond current_end, so emission is safe. By induction, the invariants hold through the scan. Emitting current once more at the end produces an equivalent union in which no pair can merge further.

def merge_intervals(intervals: list[list[int]]) -> list[list[int]]:
    if not intervals:
        return []

    ordered = sorted((start, end) for start, end in intervals)
    merged: list[list[int]] = []
    current_start, current_end = ordered[0]

    for start, end in ordered[1:]:
        if start <= current_end:
            current_end = max(current_end, end)
        else:
            merged.append([current_start, current_end])
            current_start, current_end = start, end

    merged.append([current_start, current_end])
    return merged

sorted() builds a new sorted list, and unpacking tuples does not rewrite the original inner lists, so the function honors its non-mutating contract. Comparison sorting costs O(n log n) and the scan costs O(n), for O(n log n) overall. The sorted copy and an output that may contain all n intervals are both linear, so space including output is O(n). If input is already sorted, skipping the sort gives O(n) time. If mutation is allowed, an in-place sort and write pointer can reuse the input, although the sorting implementation may still need stack or buffer space.

Validation should cover empty input, one interval, all-disjoint intervals, shared endpoints, full containment, duplicates, negative endpoints, and chained overlaps. For example, [[1, 2], [2, 3], [3, 4]] must become [[1, 4]]; it catches code that compares only adjacent raw intervals. Keep a deep copy and assert that the call does not change it. Then generate small random inputs and compare against a slow oracle that repeatedly merges any overlapping pair. The implementation above was differential-tested on 10,000 fixed-seed random cases.

For arbitrary values in a comparison model, sort and scan is the clear general answer. When n is tiny, repeated pair merging may be shorter and its slower bound may not matter. Already sorted input needs only the scan. A small bounded integer domain may justify buckets or a difference-array technique whose cost depends on the coordinate universe. In an interview, introduce such special cases only after the constraints justify them.

High-Quality Sample Answer

“I will make the boundary explicit first: the input contains unsorted closed intervals, sharing an endpoint counts as overlap, and I must return new data. That means [1, 4] and [4, 5] use a less-than-or-equal test.

A brute-force version could keep finding pairs and restarting, but the newly merged interval may overlap something seen earlier, so it may need many passes. I would sort by start and keep only one interval that is not final yet. When the next start is inside its end, I extend it with the larger end. Otherwise I write it to the result and begin a new component.

The important comparison is against the accumulated component, not just the preceding raw interval. Sorting guarantees that once the next start exceeds the current end, every later start does too, so the current result is permanently final. The emitted prefix therefore stays ordered and disjoint, while the current interval covers exactly the last merged component of the processed input.

I will use sorted() to avoid changing the caller's list and return early for empty input. The time is O(n log n) for sorting plus a linear scan, and the sorted copy and output use O(n) space. I would test touching, nested, duplicate, negative, and chained intervals, then differential-test against slow pairwise merging while also asserting that the input did not change.”

Common Mistakes

• Choosing < or <= without defining endpoint semantics → the shared-endpoint result depends on the contract → State closed versus half-open semantics and whether contiguous ranges merge before choosing the condition.
• Scanning in original order → overlapping intervals may be far apart and a future interval can reconnect emitted output → Sort by start, unless sorted input is guaranteed.
• Comparing only adjacent raw intervals → the third item in [1, 10], [2, 3], [9, 12] must meet the expanded [1, 10] → Always compare with the last merged result.
• Assigning currentend = end on overlap → a contained interval shrinks the covered range → Use max(currentend, end).
• Forgetting the final append → a loop that emits only at gaps loses the last component → Append current once after the loop.
• Reading the first item for empty input → initialization raises an index error → Return an empty list before sorting and initialization.
• Promising no mutation but sorting in place → the caller observes reordered input, and reused inner lists may keep changing → Use sorted() and new result objects, or make mutation part of the contract.
• Testing only expected arrays → chained overlaps, mutation, and boundary errors can remain hidden → Add property checks and a randomized differential oracle.
• Claiming O(n log n) is always unavoidable → sorted input and small bounded integer domains can avoid comparison sorting → Limit the lower-bound claim to unsorted arbitrary comparable endpoints.

Follow-Ups and How to Handle Them

Follow-up 1: What changes if shared endpoints do not count as overlap?

Change the condition from start <= currentend to start < currentend. Confirm the domain language first: closed intervals that share an endpoint do intersect mathematically, so a product that keeps them separate is really asking to merge only positive-length overlap. For half-open [a, b), [1, 4) and [4, 5) do not overlap; merging contiguous ranges is then another independent rule.

Follow-up 2: Input is sorted and mutation is allowed. How can you reduce extra space?

Skip sorting and compact into the input prefix with a write pointer. A read pointer visits new intervals. On overlap, update the end at the write position; on a gap, advance the write pointer and copy the new interval. Return the prefix length or a view of that prefix. The scan takes O(n) time and O(1) auxiliary space excluding the returned representation, at the cost of destroying the original input.

Follow-up 3: Intervals arrive continuously in start order. Can you emit a stream?

Yes. Keep only current. When an arriving start exceeds its end, emit current and begin the next component; emit the last component when the stream closes. Working memory is O(1) excluding output. With arbitrary arrival order, a future interval can bridge two components, so early emission is unsafe. Buffer, externally sort, or maintain a dynamic interval structure instead.

Follow-up 4: What if one hundred million intervals do not fit in memory?

Use an external sort by start: sort memory-sized batches into ordered runs, then perform a k-way merge. The merge stream is already start-ordered, so run the same one-interval state machine while merging instead of materializing a complete globally sorted file first. Comparison work remains on the order of O(n log n); disk I/O and temporary storage become the important additional costs.

Follow-up 5: Can intervals with prices or permission labels be merged directly?

Only their geometric boundaries can be unioned by this algorithm. If overlapping segments have different labels, collapsing them into one label loses information. Define whether output carries a set of labels, the highest-priority label, or minimal subsegments on which metadata is constant. The last option usually requires a sweep over endpoint events rather than a simple interval union.