Two lists of closed intervals, each sorted and pairwise disjoint, drawn as two lanes on one number line. Interval List Intersections (LC 986) walks them with one pointer per lane. Everyone draws this problem as a stack of bars and then hand-waves the pointer movement, which is backwards: the bars are scenery. The only interesting object on screen is the decision about which pointer moves, so that is what the piece draws.
At every pair (i, j) the candidate — max(starts) to min(ends) —
sits between the lanes as a teal band when it is real (a single point,
like [5,5], is real) and as a red dashed gap when it is empty. Then the
two end points are compared, the smaller one lit amber, and the lane
that ends first advances. That is safe for one reason, and the narration
says it every step: the next interval in the other lane starts after the
other lane’s current one ends, which is after this end — so the interval
that ends first can never intersect anything again. The found lane
underneath collects what was emitted.
Four ways to drive the pointers, switchable on the same instance:
- ends first — the rule above. Every intersection,
m + n − 1steps at most. - starts first — advance whichever starts first. On the LC example it happens to get everything, which is exactly why people ship it. On the “one long, many short” preset the long interval is advanced past the second and third short ones it still reached, and those intersections come up hatched red in the found lane, labelled skipped, the moment they become unreachable. No error, just a quietly incomplete answer.
- advance both — the other bug: move both pointers after every pair.
Loses
[5,5]and[24,24]on the LC example alone. - by hand — the pointers are yours. Drag a marker forward (any drag
switches to this mode), or press
a/b. Drag it three intervals at once and every pair in between is never examined; the found lane shows what that cost, and nothing stops you.
Presets: the LC example, the spanning case, and random disjoint lists up to
8 × 8. Space plays and pauses, the arrow keys step, h hands the pointers
over, r restarts.
Reuse
src/ends-first.js is a framework-free ES module:
makeDisjoint(n, span = 60)— n sorted, pairwise-disjoint, never-touching closed integer intervals in[0, span].candidate(a, b)—{ lo, hi, valid }for two closed intervals.choose(policy, a, b)—'A' | 'B' | 'both'under'end','start'or'both'.intersect(A, B)— the reference answer with provenance ({ lo, hi, i, j }).Stepper— the walk as a state machine with a history:advance(move)moves one or both pointers one step,jumpTo(lane, idx)drags one forward arbitrarily, and every frame carries the candidate, the cumulative output andlost— the true intersections the walk can no longer reach and did not emit.simulate(A, B, policy)— aStepperdriven by a policy to the end; returns{ frames, out, truth, lost, steps }. Same trace-per-tick shape ascoalesce,staircaseandsift, so a renderer can scrub in any order.
No rendering or timers in the module; the canvas demo is reference code.
Gotchas
lostis computed against the correct answer’s pair provenance, not against values: an intersection counts as found only if it was emitted at the pair that actually produces it. Buggy walks cannot produce it from any other pair anyway, since the lists are disjoint.- Under
'end', tied ends advance both pointers. That is a legal optimization, not a requirement — advancing either alone is also correct. - The lists must be pairwise disjoint and sorted for the proof to hold;
makeDisjointguarantees never-touching. Feed the module overlapping intervals within one list and'end'is no longer complete. - The demo bundles its own copy of
ends-first.js(self-contained by contract); re-copy after editingsrc/.