Coalesce — workshop

The LC 56 sort-then-sweep drawn one interval at a time on a shared number line — the running block with its end as a dashed line, the overlap test as it was made, and three switches that each break one precondition — no sort, the strict operator, an overwrite instead of a max — with the coverage the output lost hatched red.

A set of closed intervals, drawn as rows against one number line, in the order the sweep will visit them. Merge Intervals (LC 56) runs down them one row at a time. There is exactly one piece of state — the running block, a start and an end — and every visit asks it one question: next.start ≤ end? Yes: the block absorbs the interval and its end becomes max(end, next.end). No: the block is emitted to the output lane and the interval opens a new one. The block’s end is a dashed line through the input rows, so “can this one join?” is literally whether the current row starts left of that line.

The point of the piece is that the algorithm is one sentence and three preconditions, and each of the three is a switch here.

order is the one you have to manufacture. Sorted by start, an interval that cannot join the block proves that nothing after it can either, because starts only grow — that is what makes closing the block for good correct. Set it to as given and the same loop runs on the unsorted input; it closes blocks that later rows still reach into, and the output lane ends with red hatching over every stretch of input the output lost. Set it to sorted by end — the key LC 435 and LC 452 use, for a different objective — and the block’s start is no longer trustworthy either.

overlap is the operator. ≤ merges touching intervals, which is LC 56’s convention; < keeps them apart, which is the right answer for half-open intervals like meeting rooms. The touching [1,4],[4,5] preset is the whole edge-case conversation: flip the operator and the block count changes, and the readout says differs in amber rather than wrong in red, because both are defensible — you just have to say which one you implemented.

extend is the update rule. Set it to overwrite and hit contained [1,10],[2,3]: the contained interval joins the block, its end of 3 replaces the 10, the block visibly shrinks (the old extent ghosted in red), and the [4,12] that follows can no longer reach it. The output has a hole in it that the input did not.

Set n, hit new set for another random input, or the brief’s example for LC 56’s own, handed over unsorted so the sort has something to do.

Reuse

src/coalesce.js is a framework-free ES module:

makeIntervals(n, { span, rand }) — n random closed intervals with enough overlap to be interesting.
mergeIntervals(intervals, { touching }) — the plain answer, as you would write it in an interview.
orderIntervals(intervals, order) — the three visit orders.
simulate(intervals, { order, touching, update }) — one frame per visit with the incoming interval, the block before and after, the comparison as made, the action (start / extend / emit / close), the output so far, whether the block shrank, and a one-sentence note; plus the final output, LC’s expected answer, the input coverage the output lost, any overlapping output pairs, and a verdict of correct / differs / wrong. Same trace-per-tick shape as cleave, window and sift.

No rendering or timers in the module; the canvas demo is reference code.

Gotchas

differs is reserved for the strict operator: the output covers everything and is disjoint under the half-open rule, it just isn’t what LC 56 expects. Anything that loses coverage or emits overlapping blocks is wrong.
The overwrite bug is invisible on inputs with no contained interval, which is why random sets mostly pass under it — and why the preset exists.
The demo bundles its own copy of coalesce.js (self-contained by contract); re-copy after editing src/.