198. The Skyline Problem
A city block is given as an array buildings, where each entry [left, right, height] describes one rectangular building standing on flat ground: it occupies the x-range from left to right and rises to height. Buildings freely overlap, and from a distance the overlapping rectangles fuse into a single silhouette.
Return that silhouette — the skyline — as a list of key points [x, y]. Walking left to right, a key point marks an x-coordinate where the outline's height changes, and y is the new height from that x onward. The final key point always has y = 0 and marks where the rightmost building ends.
The skyline must be in its canonical form: key points sorted by x, no two key points at the same x, and no two consecutive key points with the same height (a flat stretch is represented only by its leftmost point).
Example 1:
Input: buildings = [[2, 9, 10], [3, 7, 15], [5, 12, 12], [15, 20, 10], [19, 24, 8]]
Output: [[2, 10], [3, 15], [7, 12], [12, 0], [15, 10], [20, 8], [24, 0]]
Explanation: The outline rises to 10 at x = 2, jumps to 15 when the tall building starts at x = 3, falls back to 12 when it ends at x = 7, and touches the ground at x = 12. A second group forms the shape from x = 15 to x = 24.
Example 2:
Input: buildings = [[0, 2, 3], [2, 5, 3]]
Output: [[0, 3], [5, 0]]
Explanation: The two equal-height buildings touch at x = 2, so the outline is one flat roof from 0 to 5 — the canonical form merges it into just two key points.
Constraints:
- 1 ≤ buildings.length ≤ 10⁴
- 0 ≤ left < right ≤ 2³¹ - 1
- 1 ≤ height ≤ 2³¹ - 1
Hints:
The outline only ever changes height at a building's left or right edge. Turn each building into two events and sweep the x-axis in sorted order.
While sweeping, the current outline height is the maximum height among buildings that are 'alive' at this x. You need a structure that supports insert, delete, and max — a max-heap with lazy deletion, or an ordered multiset.
Watch the tie-breaks at equal x: starts must apply before ends, taller starts before shorter ones, and shorter ends before taller ones — otherwise phantom key points appear.
Alternatively, think merge sort: the skyline of one building is trivial, and two skylines can be merged in linear time by walking both and tracking the running height of each side.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: buildings = [[2, 9, 10], [3, 7, 15], [5, 12, 12], [15, 20, 10], [19, 24, 8]]
Expected output: [[2, 10], [3, 15], [7, 12], [12, 0], [15, 10], [20, 8], [24, 0]]