Merge Intervals

The machine gets intervals like [1,3] and must return a list where overlapping or touching intervals are fused into one. The insight is that overlap detection is only cheap after sorting by start time: once sorted, an interval overlaps the previous one if its start is ≤ the previous end. Scan once and either extend the last merged interval or start a new one.

def merge(intervals):
    intervals.sort(key=lambda x: x[0])
    merged = []
    for start, end in intervals:
        if not merged or start > merged[-1][1]:
            merged.append([start, end])
        else:
            merged[-1][1] = max(merged[-1][1], end)
    return merged

Steps: (1) sort by start, (2) walk the list, (3) if the current start is past the previous end, append a new interval; otherwise widen the previous end.

Time is O(n log n) — the sort dominates; the scan itself is O(n). Space is O(n) for the merged list.

Trickiest edge case: intervals that merely touch, like [1,4] and [4,5]. The comparison is start > last_end (strict), so a start equal to the previous end merges — [1,4] and [4,5] become [1,5]. Using >= instead would wrongly keep them separate, an off-by-one that changes answers. Also, an interval fully inside another ([1,4], [2,3]) must be absorbed via max, not replaced.