0
Challenge · 33Sort & Search

Merge intervals

Patternsused in ~85% of apps

Meeting rooms, calendar clashes, booking systems, IP ranges. Interval questions look fiddly because there are so many ways two ranges can overlap, until you sort by start, at which point there is only one.

Core idea. Sort the intervals by their start time. Then walk through, keeping one interval open. Each new interval either touches the open one, in which case you stretch it, or it does not, in which case the open one is finished and a new one begins.
Playground, this isn't a screenshot
[[1,3], [8,10], [2,6], [15,18]] → sorted by start → merged
sorted by start
1, 3
2, 6
8, 10
15, 18
merged
1, 6
8, 10
15, 18

1 to 3 and 2 to 6 overlap, so they become 1 to 6. The other two touch nothing and pass through unchanged.

↑ play a little first, then dig in