Interval problems

Interval questions are common because they look different every time and are the same three moves: sort, sweep, decide what to keep. The only real decision is which endpoint to sort by.

Merge overlapping intervals — sort by start

function merge(intervals) {
  const sorted = [...intervals].sort((a, b) => a[0] - b[0]);
  const out = [];

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

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

  return out;
}

Math.max matters: the next interval may be entirely inside the current one, and overwriting the end would shrink it.

Maximum non-overlapping — sort by end

Covered in the previous lesson. Equivalently, "minimum intervals to remove" is the total minus this count. This is the erase-overlap-intervals problem.

Minimum meeting rooms — sweep the events

Split each interval into a start event and an end event, sort all events, and track how many are open at once:

function minRooms(intervals) {
  const events = [];

  for (const [start, end] of intervals) {
    events.push([start, 1]);      // a room is taken
    events.push([end, -1]);       // a room is freed
  }

  // At equal times, process the ends first — a room freed at 10 can be reused at 10.
  events.sort((a, b) => a[0] - b[0] || a[1] - b[1]);

  let open = 0;
  let peak = 0;

  for (const [, delta] of events) { open += delta; peak = Math.max(peak, open); }

  return peak;
}

The tiebreak comment is the whole question. Get it backwards and you allocate a room that was about to be released.

A heap of end times solves the same problem and generalises to "which room" — worth mentioning as the alternative.

The decision table

Half-open intervals [start, end) remove most boundary arguments. If the problem does not say whether the endpoints touch, ask — it changes the answer.