Patterns

Sort events by position; sweep across maintaining an active set

When to useSkyline problem, meeting rooms II, calendar booking, interval coverage

iterative

Line-Sweep Introduction

line_sweep_intro

Skyline problem

skyline_problem

INITIALIZE

convert intervals into start/end events; sort events

const events = [];
for (const [start, end] of intervals) {
  events.push([start, 1]);
  events.push([end + 1, -1]);
}
events.sort((a, b) => a[0] - b[0] || a[1] - b[1]);
let active = 0, max = 0;

const events = [];
for (const [left, right, height] of buildings) {
  events.push([left, -height]);
  events.push([right, height]);
}
events.sort((a, b) => a[0] - b[0] || a[1] - b[1]);
const active = new Map([[0, 1]]);
let prevMax = 0;
const result = [];

TRAVERSE

iterate events in order

for (const [, delta] of events) {

for (const [x, h] of events) {

[UPDATE]

update active set / running count based on event type

  active += delta;

  if (h < 0) {
    active.set(-h, (active.get(-h) || 0) + 1);
  } else {
    const cnt = active.get(h);
    if (cnt === 1) active.delete(h);
    else active.set(h, cnt - 1);
  }

track

record peak/transition if state changed

  if (active > max) max = active;

  const currMax = Math.max(...active.keys());
  if (currMax !== prevMax) { result.push([x, currMax]); prevMax = currMax; }

RETURN

return result (peak count, transition list, etc.)

return max;

return result;