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's O(n²). Sorting by start time removes the need entirely, since once the intervals are in time order you only ever have to compare against what you're 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.

Why sorting by start makes one pass enough: any interval that could overlap the current one has to 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, since the next interval might be entirely contained within the current one. And decide explicitly whether touching intervals like [1,3] and [3,5] count as overlapping; that's 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's 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.

You never actually need to know which train is which. Only the times matter, which is what lets the two lists be sorted independently, destroying 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 doesn't. 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