Merge Intervals

Repeatedly scan every pair of intervals; whenever two overlap, merge them into one and restart the scan. Stop when a full pass finds nothing left to merge.

class Solution:
    def merge(self, intervals: list[list[int]]) -> list[list[int]]:
        intervals = [iv[:] for iv in intervals]
        merged_any = True
        while merged_any:
            merged_any = False
            for i in range(len(intervals)):
                for j in range(i + 1, len(intervals)):
                    a, b = intervals[i], intervals[j]
                    if a[0] <= b[1] and b[0] <= a[1]:
                        a[0], a[1] = min(a[0], b[0]), max(a[1], b[1])
                        intervals.pop(j)
                        merged_any = True
                        break
                if merged_any:
                    break
        return intervals

Each pass costs O(n²) to find a mergeable pair, and up to O(n) merges may be needed — O(n³) worst case. It also never uses the fact that sorting would make overlaps trivial to spot.

Sort intervals by start time. Once sorted, any interval that overlaps the interval currently being built can only be the next one in order — so a single left-to-right sweep suffices: extend the last merged interval if the next one overlaps it, otherwise start a new one.

class Solution:
    def merge(self, intervals: list[list[int]]) -> list[list[int]]:
        intervals.sort(key=lambda iv: iv[0])
        merged = [intervals[0]]
        for start, end in intervals[1:]:
            last = merged[-1]
            if start <= last[1]:
                last[1] = max(last[1], end)
            else:
                merged.append([start, end])
        return merged

Watch the open interval stretch from [1,3] to [1,6] as the sweep moves right, and note why a gap in the sorted starts can never be repaired later.

Why it’s correct: after sorting, if the next interval’s start is beyond the current merged interval’s end, nothing later can connect back to it either (everything after only has larger starts) — so it’s safe to close off the current interval for good. Complexity: dominated by the sort → O(n log n) time; the output list holds at most n intervals → O(n) space.