56. Merge Intervals

Problem¶

Merge a list of closed intervals so that any overlapping or touching intervals become one interval, and return the merged list.

Example:

in:  [[1,3],[2,6],[8,10],[15,18]]
out: [[1,6],[8,10],[15,18]]
why: [1,3] overlaps [2,6]

Key trick¶

Sort intervals by start, then scan once while keeping the last merged interval.

Trap¶

Forgetting to sort first.
Using > instead of >=, which wrongly fails to merge touching intervals like [1,4] and [4,5].
Appending the current interval too early instead of extending the previous merged one.
Not handling intervals fully contained inside another, like [1,10] and [2,3].

Why is it interesting?¶

It is a simple pattern that tests whether you can turn an apparently pairwise-overlap problem into sorting plus one linear pass, giving \(O(n \log n)\) instead of messy repeated comparisons.

Python solution¶

class Solution:
    def merge(self, intervals: list[list[int]]) -> list[list[int]]:
        # Sort by left endpoint so any possible overlap is next to each other.
        intervals.sort(key=lambda interval: interval[0])

        merged = []

        for start, end in intervals:
            # No overlap with previous merged interval: start a new one.
            if not merged or merged[-1][1] < start:
                merged.append([start, end])
            else:
                # Overlap or touch: extend the previous interval.
                merged[-1][1] = max(merged[-1][1], end)

        return merged

Comment on my solution¶

Your solution is correct and interview-ready.
The core idea is exactly the standard optimal approach: sort, then merge in one pass.
Minor wording issue:
- Brute force is misleading here, since this is the optimal common solution, not brute force.
Minor style improvement:
- intervals.sort(...) avoids creating a second list if mutating input is acceptable.
Your overlap condition and max update are both correct, including touching intervals and containment cases.

Complexity:

Time: \(O(n \log n)\)
Space:
- \(O(n)\) for the output
- plus \(O(n)\) extra in your version because sorted(...) creates a new list

## Solution
# Works
class Solution:
    def merge(self, intervals: list[list[int]]) -> list[list[int]]:
        # [[1,3],[2,6],[8,10],[15,18]] -> [[1,6],[8,10],[15,18]]
        # Brute force:
        # - sort comparing the left bound
        # - merge consecutive intervals a, b if a_right >= b_left
        #   - carefull because b can be include in a
        sorted_intervals = sorted(intervals, key=lambda x: x[0])
        merged = [sorted_intervals[0]]
        for b in sorted_intervals[1:]:
            a = merged[-1]
            if a[1] >= b[0]:
                merged[-1] = [a[0], max(a[1], b[1])]
            else:
                merged.append(b)
        return merged


sorted([[2,6],[1,3],[15,18],[8,10]], key=lambda x: x[0]) # [[1, 3], [2, 6], [8, 10], [15, 18]]
Solution().merge([[2,6],[1,3],[15,18],[8,10]]) # [[1, 6], [8, 10], [15, 18]]
Solution().merge([[1,4],[4,5]]) # [[1, 5]]
Solution().merge([[4,7],[1,4]]) # [[1, 7]]