Merge Intervals

Pairwise merging feels natural until one merge creates a new overlap with a third interval. Then the bookkeeping branches, earlier comparisons become stale, and the implementation starts accumulating special cases.

The reliable model is simpler:

Sort first. Then let one boundary carry the proof.

Sort intervals by their start coordinate, scan from left to right, and maintain the one merged region that is still open. If the next interval starts before or at that region's end, extend the region. Otherwise, finalize it and begin another.

For inclusive intervals, the key condition is:

next_start <= current_end

That single <= decides whether touching intervals belong to the same interval union.

Read the contract and spot the pattern

Each input interval has the form [start, end]. The output must contain non-overlapping intervals that cover exactly the same ranges as the input.

For example:

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

The output is a compressed description of the same coverage. It does not lose any point covered by the input, and it does not add coverage that was absent.

The endpoint convention matters. These intervals touch:

[1,4] and [4,5]

Because both endpoints are included, they share the point 4. They must merge into:

[1,5]

Therefore, two intervals are disjoint only when:

next_start > current_end

Using < instead of <= would incorrectly leave [1,4] and [4,5] separate.

This is the interval-union problem: coalesce ranges while preserving coverage. It is different from inserting one interval into an already sorted list, choosing the maximum number of compatible intervals, or counting how many intervals are active at once. Those problems may use related data, but their obligations differ.

The recognition signal is direct:

1. The input contains intervals or ranges.
2. The output should be the smallest set of non-overlapping ranges.
3. The output must preserve the same total coverage.

When those conditions appear together, try sorting by start and scanning.

Sort first, then remove pairwise chaos

A brute-force approach compares intervals in pairs and repeatedly merges whatever overlaps. That can work on small examples, but it creates two problems.

First, it repeats comparisons. Second, a merge can enable another merge:

[1,3], [2,4], [3,8]

After merging the first two intervals into [1,4], the result overlaps [3,8]. A pairwise strategy now needs to revisit state it already examined.

Sorting removes that uncertainty. Consider:

[[1,3], [8,10], [2,6], [15,18]]

After sorting by start:

[[1,3], [2,6], [8,10], [15,18]]

Potential successors now appear in left-to-right order. Once the current merged region ends before the next interval starts, every later interval starts even farther right. There is no need to search backward or reopen the finalized region.

That is the structural reduction:

• Sorting creates the order.
• The scan maintains the state needed to merge that order.
• The current end tells us whether the next interval can connect to the existing coverage.

In Python, sorted(intervals) naturally orders two-element lists by their first element and then their second element. The algorithm only requires ordering by start, though, so using key=lambda interval: interval[0] makes that requirement explicit.

Maintain one current merged region

The result has two kinds of state:

• finalized merged intervals;
• the last result interval, which is the current region that may still expand.

The invariant is the heart of the algorithm:

After processing any prefix of the sorted intervals, merged covers exactly that prefix, contains no overlapping intervals, and is ordered by start.

Suppose the current region is:

[current_start, current_end]

and the next interval is:

[next_start, next_end]

There are only two cases.

Case 1: The intervals overlap or touch

For inclusive intervals:

next_start <= current_end

The two regions connect. Keep the current start and retain whichever end reaches farther:

current_end = max(current_end, next_end)

The max is essential. The next interval may be contained inside the current region:

current: [1,10]
next:    [3,5]

Replacing 10 with 5 would discard coverage.

Case 2: There is a strict gap

If:

next_start > current_end

the next interval cannot connect to the current region. Finalize the current region and start tracking the next one.

Because the intervals are sorted by start, every interval after next begins at or after next_start. None of them can reach backward across this gap. That is why finalizing the current region is safe.

A trace makes the state visible:

Next interval	Current region before	Comparison	Action
[2,6]	[1,3]	2 <= 3	Extend to [1,6]
[8,10]	[1,6]	8 > 6	Finalize [1,6]
[15,18]	[8,10]	15 > 10	Finalize [8,10]

At the end of the scan, the last current region still needs to remain in the result. Initializing the result with the first interval handles that naturally: every overlap updates merged[-1], and every gap appends a new region.

Prove coverage and handle touching endpoints

The algorithm is short, but the proof should be just as clear.

Initialization

After sorting, place the first interval in merged.

It covers exactly the first processed interval. The result has no overlap because it contains only one interval.

Overlap branch

Assume the invariant holds before processing [next_start, next_end], and:

next_start <= current_end

The next interval touches or overlaps the current region. Replacing the current end with:

max(current_end, next_end)

covers both regions and every point between them. The merged result still represents exactly the processed input, and no new overlap is introduced with an earlier result interval because the result was already non-overlapping and the current region is its last interval.

Disjoint branch

Now assume:

next_start > current_end

There is a strict gap. Since the input is sorted by start, all later intervals begin at or after next_start. They cannot extend leftward across the gap to reconnect with the current region.

So the current region can be finalized, and the next interval can begin a new result region. The invariant continues to hold.

Touching intervals

Run the boundary case directly:

Input: [[1,4], [4,5]]

The comparison is:

4 <= 4

That is true, so the end becomes:

max(4,5) = 5

Output:

[[1,5]]

If the problem used half-open intervals such as [start, end), equality could mean that one interval ends exactly where another begins without sharing a point. But this problem uses inclusive endpoints. Do not import half-open logic without checking the contract.

Transitive overlap

Now consider:

[[1,3], [2,4], [3,8]]

The scan behaves as follows:

1. Start with [1,3].
2. [2,4] overlaps because 2 <= 3; extend to [1,4].
3. [3,8] overlaps because 3 <= 4; extend to [1,8].

The third interval does not merely overlap the original first interval. It overlaps the already-expanded current region. That is why current_end must be updated after every merge.

Write the Python solution around the invariant

Here is a compact Merge Intervals solution in Python:

from typing import List


def merge(intervals: List[List[int]]) -> List[List[int]]:
    if not intervals:
        return []

    # Preserve the caller's input order and sort by interval start.
    ordered = sorted(intervals, key=lambda interval: interval[0])

    # Copy the first interval so the result does not alias the input interval.
    merged = [ordered[0][:]]

    for next_start, next_end in ordered[1:]:
        current = merged[-1]
        current_start, current_end = current

        if next_start <= current_end:
            # Inclusive overlap: preserve the farthest covered endpoint.
            current[1] = max(current_end, next_end)
        else:
            # A strict gap starts a new merged region.
            merged.append([next_start, next_end])

    return merged

Each line carries part of the proof:

• ordered establishes left-to-right processing.
• merged[-1] is the only region that can still connect to the next interval.
• next_start <= current_end encodes inclusive overlap.
• max(current_end, next_end) preserves all covered points.
• append records a new region only after a strict gap.

For a simpler Python implementation, sorted(intervals) is also valid because lists compare lexicographically:

ordered = sorted(intervals)

The first coordinate is compared first, so intervals are ordered by start. I prefer the explicit key in interview code because it communicates the algorithmic requirement instead of relying on a language detail.

There is also a mutation choice:

intervals.sort(key=lambda interval: interval[0])

sorts in place. It avoids creating a separate ordered list, but it changes the caller's list order. sorted(intervals, ...) leaves the input list untouched and makes that side effect impossible. Unless the contract permits mutation and it helps the implementation, I would use sorted.

One subtle Python detail is aliasing. If you write:

merged = [ordered[0]]

then merged[0] and ordered[0] refer to the same inner list. Updating merged[0][1] also updates the sorted input. That may be acceptable in some solutions, but copying the interval makes the ownership of the result clear.

Complexity, edge cases, and interview failure modes

Let n be the number of intervals.

Time complexity

Sorting costs:

O(n log n)

The scan examines each sorted interval once, so it costs:

O(n)

The total is therefore:

O(n log n)

The scan does not turn into quadratic work because it never searches backward or repeatedly compares every pair.

Space complexity

The output can contain n intervals when every input interval is disjoint, so output space is:

O(n)

In the code above, sorted(intervals) creates another list of references, which is also O(n) additional space. The inner interval copies created for the output contribute to the result itself.

If you use intervals.sort(...), you avoid the separate ordered list, but you mutate the input. The auxiliary memory used by sorting can also depend on the runtime's sorting implementation. State these separately in an interview:

• output space: O(n) in the worst case;
• extra space beyond the output: depends on whether sorting is in place and on the sorting implementation;
• for this sorted(...) version: O(n) additional list storage.

Targeted edge cases

Do not test only the polished example. Use cases that attack the state transitions:

Case	Example	What it checks
Empty input	[]	Defensive handling
One interval	[[2,5]]	Initialization
All disjoint	[[1,2], [4,5], [8,9]]	Appending new regions
All overlapping	[[1,4], [2,6], [5,9]]	Repeated extension
Nested intervals	[[1,10], [2,3], [4,8]]	Keeping max(end)
Duplicate intervals	[[2,5], [2,5]]	Equality and idempotent merging
Touching endpoints	[[1,4], [4,5]]	Inclusive comparison
Unsorted input	[[8,10], [1,3], [2,6]]	Sorting assumption

The common failures are predictable:

• assuming the input is already sorted;
• using < instead of <=;
• assigning current_end = next_end instead of taking the maximum;
• comparing the next interval with the wrong earlier interval instead of merged[-1];
• forgetting to preserve the final current region;
• appending a merged interval and then appending it again at the end;
• mutating the input accidentally when the caller expects it to remain unchanged.

Before coding, I would say the two critical lines out loud:

Disjoint means next_start > current_end.
The current end is the farthest point covered by the active merged region.

That gives the implementation a testable shape instead of leaving the loop to memory and hope.

The transferable pattern

When a problem asks for the smallest set of non-overlapping ranges that preserves the same coverage, sort by the boundary that creates a left-to-right order. Then maintain one current region whose end summarizes everything seen so far.

The next move is practical: before writing code for a new interval problem, write two sentences:

1. What exactly makes two ranges disjoint?
2. What invariant does the current state preserve?

For Merge Intervals, the answers are:

Two inclusive intervals are disjoint when next_start > current_end.
The processed result covers exactly the input seen so far, with non-overlapping ranges.

Sort first. Scan once. Let the boundary carry the proof.