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.
poke it, drag it,
try to break it
try to break it
no slides here.
you drive.
you drive.
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