Sweep Line

How to think about it

Sweep line turns a 2D interval problem into a sequence of 1D events. Imagine a vertical line sweeping left to right across the x-axis. Each interval contributes two events: an enter at its start and an exit at its end. Sort all events by coordinate, then process them in order, on enter, add the interval to an active set; on exit, remove it. The answer to “how many intervals are active at x?” or “what is the max height at x?” is a function of the active set at each event point.

The tie-breaker between events at the same coordinate matters: if intervals share an endpoint, does “end” come before “start” (no overlap) or after (overlap)? Define this explicitly per problem. For skylines, sort by height descending on enter and ascending on exit so the active set’s max updates correctly.

Template shapes

Shape	Core move	Example
Meeting rooms II	Enter +1, exit -1; track max active count	LC 253
Skyline	Active set of heights; emit on max change	LC 218
Data stream intervals	Insert/merge on event; BST or sorted list	LC 352
Perfect rectangle	Sum area + check no overlap via sweep	LC 391

Complexity baseline

O(n log n) time (sorting events), O(n) space for the active set. Each event is processed once; the active set is usually a heap or sorted structure.

From template to problem

1. Decompose each interval/rectangle into enter and exit events.
2. Sort events by coordinate; pick the tie-breaker that matches the problem’s overlap rule.
3. Process events in order: maintain the active set and the running answer.
4. Extract the answer from the active set: max count, max height, or a merged list.

/** Sweep line template: max concurrent intervals (meeting rooms II). */

export function minMeetingRooms(intervals: [number, number][]): number {
  const events: [number, number][] = [];
  for (const [start, end] of intervals) {
    events.push([start, 1]);
    events.push([end, -1]);
  }
  events.sort((a, b) => a[0]! - b[0]! || a[1]! - b[1]!);
  let active = 0, max = 0;
  for (const [, delta] of events) {
    active += delta;
    if (active > max) max = active;
  }
  return max;
}

/** Sweep line template: max concurrent intervals (meeting rooms II). */

export function minMeetingRooms(intervals: [number, number][]): number {
  const events: [number, number][] = [];
  for (const [start, end] of intervals) {
    events.push([start, 1]);
    events.push([end, -1]);
  }
  events.sort((a, b) => a[0]! - b[0]! || a[1]! - b[1]!);
  let active = 0, max = 0;
  for (const [, delta] of events) {
    active += delta;
    if (active > max) max = active;
  }
  return max;
}