Slot a new interval into a sorted, non-overlapping list. One pass in three phases: copy everything that ends before it, absorb everything that overlaps into one wider interval, then copy the rest. No sort needed: O(n).
▼The problem
LeetCode 57 (Medium). Given intervals sorted by start and non-overlapping, and one new interval, insert it so the list stays sorted and non-overlapping, merging where needed (touching ends such as [1,2] and [2,3] count as overlapping). Examples (LeetCode's): [[1,3],[6,9]], new [2,5] → [[1,5],[6,9]]; [[1,2],[3,5],[6,7],[8,10],[12,16]], new [4,8] → [[1,2],[3,10],[12,16]].
The naive way shown: append the new interval, sort everything by start, merge neighbours: O(n log n). The solution shown: one pass in three phases. Copy every interval that ends before the new one starts; absorb every interval that starts no later than the new end (new = [smaller start, larger end]); add the merged interval; copy the rest. O(n) time, O(n) for the output. The exact code on screen (CODE in src/scenes/S5.jsx):
def insert(intervals, new):
res, i, n = [], 0, len(intervals)
while i < n and intervals[i][1] < new[0]:
res.append(intervals[i])
i += 1
while i < n and intervals[i][0] <= new[1]:
new = [min(new[0], intervals[i][0]),
max(new[1], intervals[i][1])]
i += 1
res.append(new)
return res + intervals[i:]Checked in a throwaway script against append-sort-merge on 100,000 random inputs (0-5 disjoint intervals on 0-29 and a random new interval, including ones touching at an end) and on both LeetCode examples. Every value on screen comes from src/gummies.jsx: plan() replays the three phases step by step (walkthrough: [1,2] copied; [3,5] absorbed → [3,8]; [6,7] absorbed, still [3,8]; [8,10] touches at 8 → [3,10]; [12,16] starts after 10, stop; answer [1,2] [3,10] [12,16]) and brute() sorts and merges; the module re-checks plan = brute on 4,000 seeded random inputs and all of the scenes' values when it loads, and every scene asserts the values it shows. src/gen_score.py keys its hop, squish and drop sounds to the same moves. The sort-then-merge shape of ../merge-intervals is what scene 3 calls the naive way.
The solution
def insert(intervals, new):
res, i, n = [], 0, len(intervals)
while i < n and intervals[i][1] < new[0]:
res.append(intervals[i])
i += 1
while i < n and intervals[i][0] <= new[1]:
new = [min(new[0], intervals[i][0]),
max(new[1], intervals[i][1])]
i += 1
res.append(new)
return res + intervals[i:]Transcript
Insert Interval. You get sorted, non-overlapping intervals and one new interval. Insert it so the list stays sorted with no overlaps, merging wherever they touch.
Take one to three and six to nine, with the new interval two to five. It overlaps one to three, so they merge into one to five. The answer: one to five, six to nine.
The naive way: append the new interval, sort everything, then merge neighbors. That sort costs n log n, though the list was already sorted.
The key idea: one pass, in three phases. Copy every interval that ends before the new one starts. Absorb every interval that overlaps it, keeping the smaller start and the larger end. Add the merged interval, then copy the rest.
In code, an index walks the list. The first loop copies intervals that end too early. The second runs while an interval starts no later than the new end, widening the new interval. Append it, then everything left.
A longer example: one to two, three to five, six to seven, eight to ten, twelve to sixteen. The new interval: four to eight. One to two ends before four: copy it. Three to five overlaps: three to eight. Six to seven fits inside. Eight to ten touches at eight: three to ten. Twelve starts after ten: stop. Add three to ten, then copy twelve to sixteen. The answer: one to two, three to ten, twelve to sixteen.
Each interval is looked at once: linear time, and linear space for the output.
Copy, absorb, copy. That's Insert Interval.