Hints — p46 Merge Intervals

Hint 1. ASK first: do [1, 2] and [2, 3] merge? (LC 56: yes — closed intervals.) The answer changes one operator (<= vs <).

Hint 2. Without sorting, overlap detection is O(n²) per pair. SORT by start first. After sorting, all overlapping intervals are CONTIGUOUS in the array.

Hint 3. Sweep idea: walk the sorted array; for each interval, either extend the last-appended interval (if they overlap) or append a new one.

out = [first]
for s, e in rest:
    if s <= out[-1][1]: out[-1][1] = max(out[-1][1], e)
    else: out.append([s, e])

Hint 4. The max(out[-1][1], e) is critical. Naïve out[-1][1] = e FAILS on the contained case: [[1, 10], [2, 3]] would give [1, 3] instead of [1, 10].

Hint 5. Why is comparing only out[-1] (not all of out) enough? Because out is sorted with disjoint intervals: any earlier interval ended before out[-1] started, so if current doesn’t overlap out[-1], it definitely doesn’t overlap anything earlier either.

If still stuck: see solution.py.