Merge Intervals

Problem

You are given a list of closed integer intervals intervals, where intervals[i] = [start, end] with start <= end, in no particular order. Two intervals overlap if they share at least one point (so [1,4] and [4,5] overlap, because they share 4). Combine every group of mutually reachable overlapping intervals into a single interval and return the resulting list, sorted by start.

• Up to around ten thousand intervals.
• Endpoints are non-negative and fit comfortably in a normal int, with start <= end.

Examples

• [[2,5],[4,9],[12,15],[20,25]] → [[2,9],[12,15],[20,25]]. Only the first two overlap.
• [[3,6],[6,8]] → [[3,8]]. Sharing the single point 6 counts as overlapping.
• [[3,6],[1,4],[5,9]] → [[1,9]]. After sorting, each interval overlaps the running merged one, so everything collapses to one.

Hints

1. If the intervals were sorted by start, which neighbors could possibly overlap?
2. Walk the sorted list keeping just the interval you are currently building. When does the next interval extend it, and when does it start a new one?
3. Sort by start, then a single linear sweep comparing each interval's start with the end of the last merged interval.