Merging Intervals

Five meetings in a calendar:

const meetings = [[1, 3], [2, 6], [8, 10], [9, 12], [15, 18]];

Collapse the ones that overlap into single blocks of busy time. By eye: 1–6, then 8–12, then 15–18.

Why the obvious way is awkward

Compare every pair, merge the ones that touch, repeat until nothing changes.

That is $O(n^2)$ per pass, and worse, merging can create new overlaps — a freshly widened block may now reach a block you already checked — so you need the outer “repeat until stable” loop as well. It is fiddly to write and easy to get subtly wrong.

The realisation

Sort by start time first.

Once the list is in start order, an interval can only ever overlap the block you are currently building. Anything before that is finished, permanently, and you never look at it again.

That gives one pass after the sort, and a single comparison per interval:

if (current.start <= lastBlock.end) …

The code

type Interval = [start: number, end: number];

function merge(intervals: Interval[]): Interval[] {
  if (intervals.length === 0) return [];

  const sorted = [...intervals].sort((a, b) => a[0] - b[0]);
  const out: Interval[] = [[...sorted[0]!] as Interval];

  for (const [start, end] of sorted.slice(1)) {
    const last = out[out.length - 1]!;

    if (start <= last[1]) last[1] = Math.max(last[1], end);   // overlap: extend
    else out.push([start, end]);                              // gap: new block
  }

  return out;
}

$O(n \log n)$, all of it in the sort. The sweep itself is linear.

< or <=: decide it deliberately

Do [1, 3] and [3, 5] overlap?

It depends what the numbers mean, and this is a question to ask out loud rather than guess:

• Meeting times. A meeting ending at 3 and one starting at 3 do not clash — use <, keep them separate.
• Occupied ranges. If 3 is in both, they touch — use <=, merge them.
• Half-open ranges [start, end), which is how most range APIs work — the first interval covers up to but not including 3, so < is right.

Half-open is worth defaulting to. [1,3) and [3,5) sit next to each other with no gap and no overlap, adjacent ranges tile perfectly, and length is just end - start with no + 1 anywhere.

The same sweep, other questions

The sort-then-sweep shape answers a family of problems, and once you see it the variations are small:

Insert one interval into a merged list. Everything ending before the new start passes through; everything overlapping is absorbed; everything starting after the new end passes through. Three loops, no sort — the list was already sorted.

How many meetings run at once? Do not merge. Split each interval into two events, sort them, and sweep a counter:

const events = intervals.flatMap(([s, e]) => [[s, +1], [e, -1]] as const);
events.sort((a, b) => a[0] - b[0] || a[1] - b[1]);   // ← the tiebreak matters

let running = 0;
let peak = 0;
for (const [, delta] of events) peak = Math.max(peak, (running += delta));

That tiebreak decides the touching case again: with −1 before +1, a meeting ending at 3 frees the room for one starting at 3. Flip it and you need an extra room you do not need. Same decision as < versus <=, wearing a different hat.

Free gaps. Merge, then read the space between consecutive blocks.

Minimum removals to make everything disjoint. Here sort by end, not start, and greedily keep the interval that finishes soonest — that leaves the most room for what follows. This is a greedy argument rather than a sweeping one, and the change of sort key is the tell.