LeetCode 56: Merge Intervals

Problem Restatement

We are given an array of intervals.

Each interval has a start and an end:

[start, end]

We need to merge all overlapping intervals and return a list of non-overlapping intervals that covers the same ranges as the original input.

Two intervals overlap when the next interval starts before or exactly when the current interval ends.

For example:

[1, 4] and [4, 5]

These overlap because they touch at 4, so they merge into:

[1, 5]

The official constraints are 1 <= intervals.length <= 10^4, intervals[i].length == 2, and 0 <= start_i <= end_i <= 10^4.

Input and Output

Function shape:

def merge(intervals: list[list[int]]) -> list[list[int]]:
    ...

Examples

For:

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

The intervals [1, 3] and [2, 6] overlap because:

2 <= 3

So they merge into:

[1, 6]

The intervals [8, 10] and [15, 18] do not overlap with anything.

The answer is:

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

For:

intervals = [[1, 4], [4, 5]]

The two intervals touch at endpoint 4, so they count as overlapping.

The answer is:

[[1, 5]]

First Thought: Compare Every Pair

A direct approach is to compare every interval with every other interval.

If two intervals overlap, merge them. Then repeat until no more intervals can be merged.

This is difficult to implement cleanly because merging one pair can create a new interval that overlaps with another pair. We may need many passes.

There is a simpler approach if we first sort the intervals.

Key Insight

Sort intervals by start time.

After sorting, any interval that can overlap the current merged interval must appear next to it or later in the list.

So we can scan from left to right and maintain the last merged interval.

For each new interval [start, end]:

1. If start is greater than the end of the last merged interval, there is no overlap.
2. Otherwise, the intervals overlap, so extend the last merged interval.

The merge rule is:

merged[-1][1] = max(merged[-1][1], end)

Why max is needed:

[1, 10] and [2, 3]

These overlap, but the merged end should stay 10.

Algorithm

Sort the intervals:

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

Create an empty result list:

merged = []

For each interval:

1. If merged is empty, append the interval.
2. Otherwise, compare the current interval with the last merged interval.
3. If the current interval starts after the last merged interval ends, append it.
4. Otherwise, merge it by updating the last end.

Return merged.

Correctness

After sorting, intervals are processed in nondecreasing order of start time.

The algorithm keeps merged as a list of non-overlapping intervals that covers all intervals processed so far.

When the next interval starts after the end of the last merged interval, it cannot overlap that last interval. Since all future intervals start at the same position or later, this interval should begin a new merged range. Appending it is correct.

When the next interval starts before or exactly at the end of the last merged interval, the two intervals overlap. Their union is covered by keeping the same start and updating the end to the larger of both ends. This preserves coverage and keeps the result non-overlapping.

By processing every interval once after sorting, the algorithm covers every input interval and merges exactly the overlapping ones. Therefore the returned intervals are correct.

Complexity

Depending on the sorting implementation, sorting may also use extra space.

Implementation

class Solution:
    def merge(self, intervals: list[list[int]]) -> list[list[int]]:
        intervals.sort(key=lambda x: x[0])

        merged = []

        for start, end in intervals:
            if not merged or start > merged[-1][1]:
                merged.append([start, end])
            else:
                merged[-1][1] = max(merged[-1][1], end)

        return merged

Code Explanation

First, sort intervals by their start:

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

This makes overlapping intervals appear close together.

Then create the answer list:

merged = []

For each interval:

for start, end in intervals:

If merged is empty, we add the first interval.

If the current interval starts after the last merged interval ends, there is no overlap:

if not merged or start > merged[-1][1]:
    merged.append([start, end])

Otherwise, the intervals overlap.

We extend the last merged interval:

merged[-1][1] = max(merged[-1][1], end)

Finally, return the merged list:

return merged

Testing

def run_tests():
    s = Solution()

    assert s.merge([[1, 3], [2, 6], [8, 10], [15, 18]]) == [
        [1, 6],
        [8, 10],
        [15, 18],
    ]

    assert s.merge([[1, 4], [4, 5]]) == [[1, 5]]

    assert s.merge([[1, 4]]) == [[1, 4]]

    assert s.merge([[1, 4], [0, 2], [3, 5]]) == [[0, 5]]

    assert s.merge([[1, 10], [2, 3], [4, 8]]) == [[1, 10]]

    assert s.merge([[1, 2], [3, 4], [5, 6]]) == [
        [1, 2],
        [3, 4],
        [5, 6],
    ]

    print("all tests passed")

run_tests()