Merge Intervals

Intuition

If the intervals are lined up by their start point, then any interval that overlaps a given one must appear right after it. That lets us keep a single 'current' interval and either stretch its end when the next interval bleeds into it, or push a brand new interval when there is a clean gap. One left-to-right pass is enough because sorting has already grouped everything that could possibly connect.

Algorithm walkthrough

1. 1Sort the input intervals in ascending order of their start value.
2. 2Create an empty result list and iterate over each interval [start, end].
3. 3If the result is empty or the current start is greater than the end of the last kept interval, append [start, end] as a new block.
4. 4Otherwise there is an overlap, so raise the end of the last kept interval to the max of its end and the current end.
5. 5After the pass, the result holds every merged, non-overlapping interval.

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 merged and start <= merged[-1][1]:
                merged[-1][1] = max(merged[-1][1], end)
            else:
                merged.append([start, end])
        return merged