Interval Problems: Merging and Minimum Platforms

Interval problems look like they need every pair compared: does booking A clash with booking B, for all A and B? That is O(n²). Sorting by start time removes the need entirely, because once the intervals are in time order you only ever have to compare against what you are currently holding.

Merging overlapping intervals

Sort by start time. Walk the list holding one "current" interval. For each next interval, either it starts after the current one ends, in which case the current interval is finished and you emit it and start a new one, or it overlaps, in which case you extend the current end to the maximum of the two.

The reason sorting by start makes one pass sufficient: any interval that could overlap the current one must start at or before the current end, and since starts are ascending, once you find one that starts later, no later interval can overlap either.

Two details catch people out. Use max(current.end, next.end) rather than next.end, because the next interval may be entirely contained within the current one. And decide explicitly whether touching intervals like [1,3] and [3,5] count as overlapping; that is a specification question, not an algorithmic one, and it changes > to >=.

Minimum platforms

Given arrival and departure times, how many platforms does a station need so no train ever waits? Equivalently: how many meeting rooms, how many servers, what is the peak concurrency.

The insight is that arrivals and departures can be considered separately. Sort both lists, then walk them together in time order: an arrival increments the count of things in use, a departure decrements it. The answer is the maximum the counter ever reaches.

Switch the widget above to "Minimum platforms" and watch the counter. This is the merge two-pointer sweep again, over two sorted lists of times.

Note that you never need to know which train is which. Only the times matter, which is what allows the two lists to be sorted independently and destroys the pairing entirely.

The tie-breaking rule matters: if a departure and an arrival happen at the same instant, does the platform free up in time? Handle the departure first and it does; handle the arrival first and it does not. Both are defensible, and the problem statement has to say which.

In code

function mergeIntervals(intervals) {
  if (intervals.length === 0) return [];
  const sorted = [...intervals].sort((a, b) => a.start - b.start);
  const out = [{ ...sorted[0] }];

  for (const cur of sorted.slice(1)) {
    const last = out[out.length - 1];
    if (cur.start > last.end) {
      out.push({ ...cur });          // no overlap: start a new interval
    } else {
      // max, not cur.end: cur may be entirely inside last.
      last.end = Math.max(last.end, cur.end);
    }
  }
  return out;
}

function minimumPlatforms(intervals) {
  const arrivals = intervals.map((i) => i.start).sort((a, b) => a - b);
  const departures = intervals.map((i) => i.end).sort((a, b) => a - b);

  let i = 0, j = 0, inUse = 0, peak = 0;
  while (i < arrivals.length) {
    if (arrivals[i] <= departures[j]) {
      inUse++;
      peak = Math.max(peak, inUse);
      i++;
    } else {
      inUse--;
      j++;
    }
  }
  return peak;
}

Check yourself