025. Merge Overlapping Intervals

Bridge · Download this solution · All solutions and shared helpers

Problem

Given closed intervals [start,end] with start<=end, return their union as sorted, pairwise disjoint closed intervals. Sharing an endpoint counts as overlap. Inputs may be unsorted; return fresh two-element lists without mutating the supplied intervals.

Examples

Example 1

merge_intervals([[1, 3], [2, 6], [8, 10]])
=> [[1, 6], [8, 10]]

The first two intervals overlap.

Example 2

merge_intervals([])
=> []

The union of no intervals is empty.

Example 3

merge_intervals([[1, 5], [2, 3], [5, 7]])
=> [[1, 7]]

Containment and endpoint contact both preserve one union interval.

Reveal the worked solution and reasoning

Why this mechanism works

Sorting by start ensures that a new interval cannot reach backward past a completed gap. Keep the last output interval active. If the next start is within it, only its end may need extension. Otherwise a permanent gap has been found and a new interval begins.

State and boundaries

output is a sorted merged prefix. Its last interval remains extendable; earlier intervals are final.

Protocol

Sort by start.
Start an output interval when there is a gap.
Otherwise extend the active end with max.
Return the merged intervals.

Visualization

[1---3]
  [2------6]     [8--10]
=> [1------6]    [8--10]

Python implementation

def merge_intervals(intervals):
    output = []
    for start, end in sorted(intervals):
        if not output or start > output[-1][1]:
            output.append([start, end])
        else:
            output[-1][1] = max(output[-1][1], end)
    return output

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

merge_intervals([[1, 3], [2, 6], [8, 10]])

L2 merge_intervals: output = []
intervals=[[1, 3], [2, 6], [8, 10]]; output=[]

L3 merge_intervals: for start, end in sorted(intervals):
intervals=[[1, 3], [2, 6], [8, 10]]; output=[]; start=1; end=3

L5 merge_intervals: output.append([start, end])
intervals=[[1, 3], [2, 6], [8, 10]]; output=[[1, 3]]; start=1; end=3

L3 merge_intervals: for start, end in sorted(intervals):
intervals=[[1, 3], [2, 6], [8, 10]]; output=[[1, 3]]; start=2; end=6

L7 merge_intervals: output[-1][1] = max(output[-1][1], end)
intervals=[[1, 3], [2, 6], [8, 10]]; output=[[1, 6]]; start=2; end=6

L3 merge_intervals: for start, end in sorted(intervals):
intervals=[[1, 3], [2, 6], [8, 10]]; output=[[1, 6]]; start=8; end=10

L5 merge_intervals: output.append([start, end])
intervals=[[1, 3], [2, 6], [8, 10]]; output=[[1, 6], [8, 10]]; start=8; end=10

Result: [[1, 6], [8, 10]]. The first two intervals overlap.

merge_intervals([])

L2 merge_intervals: output = []
intervals=[]; output=[]

Result: []. The union of no intervals is empty.

Why the solution is correct

With nondecreasing starts, a gap before the next interval can never be filled by a later interval starting even farther right. Overlap can therefore be resolved locally against the active interval. Extension preserves the union, and committing a gap preserves disjointness.

Time and space

O(n log n) time and O(n) storage for sorting and output.

Common mistakes

Replacing the end instead of taking max shrinks a containing interval. For closed intervals, equality at an endpoint must merge.

Reasoning card

State: output is a sorted merged prefix. Its last interval remains extendable; earlier intervals are final.

Invariant: Committed intervals are final and disjoint from the active interval.

Decision to rehearse: Sort by start; extend current interval or commit it.

Finish: Return the merged intervals

Transfer exercise

Change the contract to half-open intervals and decide whether touching intervals should be coalesced as an output representation.