The Skyline Problem

Problem Given the positions and heights of a set of rectangular buildings standing on a flat ground line, output the skyline they form when viewed from a distance: the list of key points [x, height] at every x where the visible outline height changes.

Input / Output

• Input: buildings[i] = [left_i, right_i, height_i], sorted by left edge.
• Output: the skyline as a list of [x, height] key points in ascending x, each marking a height change. The final point always has height 0.

Constraints

• 1 <= n <= 10^4; coordinates can reach ~2^31.
• No two consecutive output points may share a height — collinear segments must be merged away.
• Buildings may overlap partially, nest entirely inside a taller one, or share exact edges.

Example

• buildings = [[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]] → [[2,10],[3,15],[7,12],[12,0],[15,10],[20,8],[24,0]].
• The instructive cases: at x=7 the tallest building ends but the skyline drops only to the next-tallest still-active height (12, not 0); at x=12 nothing is active so it falls to 0; and two equal-height buildings touching at an edge must not emit a duplicate point.