Merging and Sorting Intervals

Meeting rooms, calendar bookings, memory ranges, video segments. They are all the same problem: pairs of numbers on a line that may or may not overlap.

Sort first, almost always

Sorting by start time turns a problem about arbitrary pairs into a single left-to-right sweep. Once sorted, an interval can only overlap the one immediately before it - so a single pass is enough, and the cost is dominated by the O(n log n) sort.

function merge(intervals) {
  if (intervals.length <= 1) return [...intervals]

  const sorted = [...intervals].sort((a, b) => a[0] - b[0])
  const merged = [sorted[0].slice()]

  for (let i = 1; i < sorted.length; i++) {
    const [start, end] = sorted[i]
    const last = merged[merged.length - 1]

    if (start <= last[1]) {
      last[1] = Math.max(last[1], end)   // overlaps: extend
    } else {
      merged.push([start, end])          // gap: start a new one
    }
  }

  return merged
}

console.log(merge([[1, 3], [2, 6], [8, 10], [15, 18]]))
// [[1, 6], [8, 10], [15, 18]]

Math.max matters: [1, 9] followed by [2, 3] must stay [1, 9]. Assigning end directly would wrongly shrink it, and this is the usual bug.

Two intervals overlap when

a.start < b.end && b.start < a.end. Writing the condition this way - rather than enumerating the cases where they do not - avoids a tangle of four comparisons. Decide early whether touching endpoints count as overlapping, because [1, 2] and [2, 3] are a boundary case every one of these problems has an opinion about.

The sweep line

When the question is "how many at once" rather than "merge these", split each interval into two events and sort them together: +1 at each start, −1 at each end. Sweeping through while keeping a running total gives the maximum concurrency, which is the minimum number of meeting rooms.

function minRooms(meetings) {
  const events = []
  for (const [start, end] of meetings) {
    events.push([start, 1])
    events.push([end, -1])
  }

  // Ends before starts at the same instant: a room frees up first.
  events.sort((a, b) => a[0] - b[0] || a[1] - b[1])

  let active = 0
  let peak = 0
  for (const [, delta] of events) {
    active += delta
    peak = Math.max(peak, active)
  }

  return peak
}

console.log(minRooms([[0, 30], [5, 10], [15, 20]]))  // 2

The tie-break in the sort is the whole subtlety. A meeting ending at 10 and another starting at 10 need one room, not two - processing the −1 first is what expresses that.