Merge Intervals (LeetCode 56)

The problem

Given a list of intervals [start, end], merge every group of overlapping intervals and return the resulting list of non-overlapping intervals. Intervals that touch (one ends where the next starts) count as overlapping.

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

[1, 3] and [2, 6] overlap (2 ≤ 3), so they merge into [1, 6]. The others stand alone.

How to think about it

Start with brute force. Repeatedly scan all pairs, merge any two that overlap, and restart until nothing changes. Each round is O(n²) and there can be up to n rounds.

The key insight: sort by start, and overlaps only happen with the block you just built. Once the intervals are in start order, the next interval either overlaps the last merged interval or starts after it ends. It cannot overlap an earlier merged block, because those all end before the last one starts. So you only ever look at res[-1].

Extend with max, not with the new end. When the next interval overlaps, the merged block ends at max(res[-1][1], e). The new interval might sit entirely inside the current block (like [2, 3] inside [1, 6]), so blindly taking e would shrink it.

Which pattern is this? Merge intervals, the namesake of the lesson. The tell is “overlapping intervals” plus “merge” or “combine”.

Approach

1. Sort the intervals by start.
2. Walk them. If res is non-empty and the current start s is at most res[-1][1], they overlap: set res[-1][1] = max(res[-1][1], e).
3. Otherwise there is a gap: append [s, e] as a new block.
4. Return res.

Solution

def merge(intervals):
    intervals.sort()                              # by start
    res = []
    for s, e in intervals:
        if res and s <= res[-1][1]:               # overlaps the last merged block
            res[-1][1] = max(res[-1][1], e)       # extend it (max handles nesting)
        else:
            res.append([s, e])                    # gap: start a new block
    return res
# merge([[1,3],[2,6],[8,10],[15,18]]) -> [[1,6],[8,10],[15,18]]

Dry run

Sorted input: [[1, 3], [2, 6], [8, 10], [15, 18]].

Complexity

• Time: O(n log n). Sorting dominates; the sweep is O(n).
• Space: O(n). The output can hold all n intervals when none overlap.

Edge cases and pitfalls

• Empty input returns [].
• Touching intervals such as [[1, 4], [4, 5]] merge into [[1, 5]] because of <=.
• Nested intervals such as [[1, 10], [2, 3]] stay [[1, 10]]; forgetting max would wrongly produce [[1, 3]].
• Not sorting first is the most common bug: [[8, 10], [1, 3], [2, 6]] would never merge 1–3 with 2–6 properly.
• Aliasing: res.append([s, e]) creates a new list, so extending it does not modify the caller’s interval objects.

Related problems

• Insert Interval (LeetCode 57): the list is already sorted, so you merge just one new interval in O(n).
• Employee Free Time (LeetCode 759): merge everyone’s intervals, then report the gaps.
• Remove Covered Intervals (LeetCode 1288): a sort-then-sweep that checks containment instead of overlap.