Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Hardsweep-line

The Skyline Problem

Problem (restated)

Buildings are [left, right, height] axis-aligned rectangles on the ground. Return the skyline as key points [x, height]: every x where the silhouette height changes, in left-to-right order, ending at height 0.

Intuition

Sweep left to right. Each building is an enter at left (add height) and an exit at right (remove). The skyline only emits when the max active height changes. Tie-break at the same x: process enters before exits (a building starting where another ends should not dip to 0), and taller enters first.

Approaches

Sweep + active heights

Unverified

Time O(n log n)Space O(n)

Idea. Events (x, −h, id) start and (x, +h, id) end; sort. A live set + max-heap (lazy delete) of heights, plus a ground height 0. After all events at x, if max ≠ last emitted height, append [x, max].

Walkthrough. [[2,9,10],[3,7,15]] emits [2,10], then [3,15], then [7,10], then [9,0].

Trade-offs. Lazy heap deletion is the usual interview version. Removing from a real multiset is cleaner in C# (SortedDictionary). Sort key is the overlap rule: start-before-end at the same x.

Solution

export function getSkyline(buildings: number[][]): number[][] {
  const events: [number, number, number][] = [];
  for (let i = 0; i < buildings.length; i++) {
    const [l, r, h] = buildings[i]!;
    events.push([l, -h, i]);
    events.push([r, h, i]);
  }
  events.sort((a, b) => a[0]! - b[0]! || a[1]! - b[1]! || a[2]! - b[2]!);
  const live = new Set<number>([-1]);
  const heap: [number, number][] = [[0, -1]];
  const res: number[][] = [];
  let i = 0;
  while (i < events.length) {
    const x = events[i]![0]!;
    while (i < events.length && events[i]![0] === x) {
      const h = events[i]![1]!;
      const id = events[i]![2]!;
      if (h < 0) {
        live.add(id);
        heap.push([h, id]);
      } else {
        live.delete(id);
      }
      i++;
    }
    heap.sort((a, b) => a[0]! - b[0]!);
    while (heap.length && !live.has(heap[0]![1]!)) heap.shift();
    const maxH = -heap[0]![0]!;
    if (!res.length || res[res.length - 1]![1] !== maxH) res.push([x, maxH]);
  }
  return res;
}

export function getSkyline(buildings: number[][]): number[][] {
  const events: [number, number, number][] = [];
  for (let i = 0; i < buildings.length; i++) {
    const [l, r, h] = buildings[i]!;
    events.push([l, -h, i]);
    events.push([r, h, i]);
  }
  events.sort((a, b) => a[0]! - b[0]! || a[1]! - b[1]! || a[2]! - b[2]!);
  const live = new Set<number>([-1]);
  const heap: [number, number][] = [[0, -1]];
  const res: number[][] = [];
  let i = 0;
  while (i < events.length) {
    const x = events[i]![0]!;
    while (i < events.length && events[i]![0] === x) {
      const h = events[i]![1]!;
      const id = events[i]![2]!;
      if (h < 0) {
        live.add(id);
        heap.push([h, id]);
      } else {
        live.delete(id);
      }
      i++;
    }
    heap.sort((a, b) => a[0]! - b[0]!);
    while (heap.length && !live.has(heap[0]![1]!)) heap.shift();
    const maxH = -heap[0]![0]!;
    if (!res.length || res[res.length - 1]![1] !== maxH) res.push([x, maxH]);
  }
  return res;
}

Template connection

Skyline shape of Sweep Line: enter/exit events, active set of heights, emit on max change. LC 253 is the same sweep with a count instead of a height multiset.

Reflection

A start is (x, -h) and an end is (x, +h). At the same x, the start sorts first. Processing the end first drops the height to the ground and emits a false point.
After every event at x, if the live maximum changed, write [x, max]. The ground height is 0. An end removes that building from the live set.
Overlapping roofs collapse to the max. Two adjacent buildings of the same height do not emit a point between them. An empty skyline writes nothing.