pattern heroPT–23LeetCode Extension

Intervals

Sort the intervals by start, and the ones that overlap end up next to each other. Then each interval is compared only with the one before it, not with all the others.

Variant
P06 IntervalsMerge · 1×

Example problem: merge the overlapping intervals in [6, 9], [1, 3], [11, 12], [7, 8], [2, 5], [8, 10].

[1, 3][2, 5][6, 9][7, 8][8, 10][11, 12]merged0123456789101112
not looked at yetcurrent intervallast merged intervalmerged resultalready handled

Sort by start: 1, 2, 6, 7, 8, 11

merged = –start = –end = –last = –
01/26
restart · back · play · step
Speed
1function mergeIntervals(intervals):
2 sort intervals by start
3 merged = [intervals[0]]
4 for each [start, end] after the first:
5 last = last interval in merged
6 if start > last.end:
7 add [start, end] to merged
8 else:
9 last.end = max(last.end, end)
10 return merged

← → step · space play/pause

How to recognise

a list of [start, end] pairs, such as meetings or bookings, and a question about what overlaps.

How to solve problems like this

  1. Sort by start. To keep as many non-overlapping intervals as possible, sort by end instead.
  2. Decide whether intervals that only touch overlap: start ≤ last end, or start < last end.
  3. Walk once and compare each interval only with the last one you kept: extend it or start a new one.
  4. To count how many overlap at once, turn each interval into +1 at its start and −1 at its end, sort these points and keep a running sum.

Variant: Sort by end

The same, but sort by end. That is how you pick the most intervals that do not overlap, or the fewest points that hit them all: the interval that ends first leaves the most room for the rest.

  1. Sort by end when you choose points or intervals greedily and the one that ends first should go first.
  2. Keep only the last choice: here the last shot, the end of the interval it was made for.
  3. An interval that starts after it needs a new choice at its own end. Anything else is already covered, so skip it.
  4. To keep the most intervals that do not overlap, sort by end the same way: keep an interval if it starts after the end of the last kept one, and drop the rest.

Where it's used

  • Video in the browser. The browser keeps track of which parts of a video are already downloaded as a list of time ranges. Ranges that overlap or touch are merged into one, so the list stays short and sorted.
  • Genomics. bedtools merge joins overlapping stretches of a genome. The file is sorted by start first, and then each stretch is compared only with the previous one.
  • PostgreSQL. PostgreSQL can store ranges of dates and numbers. The range_agg function gathers many ranges into a set with no overlaps, merging the ones that overlap.