Merge Intervals

You'll sort the intervals by start, then merge each one into the last group in a single pass. You need sorting. Related chapter: intervals.

1. The problem

You get a list of intervals [start, end], in any order, each with start ≤ end. Merge the ones that overlap, and return intervals that don't overlap and cover exactly the same numbers. Intervals that only touch, like [1,3] and [3,5], count as overlapping. Don't change the input. This is LeetCode 56. Our function also handles an empty list.

2. A correct baseline

def baseline(intervals):
    parts=[pair.copy() for pair in intervals]
    changed=True
    while changed:
        changed=False
        for i in range(len(parts)):
            for j in range(i+1,len(parts)):
                if max(parts[i][0],parts[j][0])<=min(parts[i][1],parts[j][1]):
                    parts[i]=[min(parts[i][0],parts[j][0]),max(parts[i][1],parts[j][1])]
                    parts.pop(j)
                    changed=True
                    break
            if changed:
                break
    return sorted(parts)

assert baseline([[8,10],[1,3],[2,6]])==[[1,6],[8,10]]
assert baseline([[1,3],[3,5]])==[[1,5]]
assert baseline([])==[]

Each merge restarts a search over all pairs, and there can be n − 1 merges. So this takes up to O(n³) time: the work grows with the cube of the number of intervals. On 1,000 intervals, that's up to a billion comparisons. It uses O(n) space.

The bottleneck. After every merge, it searches every pair again for the next overlap.

3. The observation

Sort [[8,10],[1,3],[2,6]] by start: [1,3], [2,6], [8,10]. Now each interval can only overlap the group just before it. [2,6] starts at 2, inside [1,3], so they merge into [1,6]. [8,10] starts after 6, so it begins a new group.

Why only the last group? Older groups all end before the last group starts, and every later interval starts even later. So once a group is behind you, nothing can reach it.

When an interval overlaps the last group, set the group's end to the larger of the two ends. Don't just take the new end: [2,3] inside [1,10] must not shrink it.

4. The solution and a trace

class Solution:
    def merge(self, intervals: list[list[int]]) -> list[list[int]]:
        """Inclusive intervals, start <= end; return new sorted pairs."""
        merged=[]
        for start,end in sorted(intervals):
            if not merged or start>merged[-1][1]:
                merged.append([start,end])
            else:
                merged[-1][1]=max(merged[-1][1],end)
        return merged

solve=Solution().merge
assert solve([[8,10],[1,3],[2,6]])==[[1,6],[8,10]]
assert solve([[1,3],[3,5]])==[[1,5]]
assert solve([])==[]

Trace [[8,10],[1,3],[2,6]] after sorting:

5. Why it works

What stays true. The output is sorted, has no overlaps, and covers exactly the numbers of the intervals read so far.

Why each step keeps it true. An interval that starts after the last group's end can't overlap anything, so it starts a new group. One that overlaps extends the last group to cover both. Because starts are sorted, no older group ever needs to change.

6. Cost, edge cases, and failure

Cost. Sorting takes O(n log n) time, and the merge pass takes O(n). The sorted copy and the output take O(n) space.

Edge cases. Equal starts, one-number intervals like [4,4], and intervals inside other intervals all work. Negative numbers work too, though LeetCode doesn't use them. Touching intervals overlap, so a new group starts only when start > end, not start >= end.

Where it fails. Taking the new end instead of the larger end, or treating touching intervals as separate, gives wrong answers:

assert solve([[1,10],[2,3]])==[[1,10]]  # Assigning end=3 would incorrectly shrink coverage.
assert solve([[1,3],[3,5]])==[[1,5]]  # Treating equality as disjoint changes the contract.

import random,copy
rng=random.Random(56)
for _ in range(500):
    intervals=[]
    for _ in range(rng.randrange(10)):
        a,b=sorted([rng.randint(0,15),rng.randint(0,15)])
        intervals.append([a,b])
    before=copy.deepcopy(intervals)
    assert solve(intervals)==baseline(intervals)
    assert intervals==before