The Skyline Problem

Given the x-coordinates and heights of buildings, return the skyline formed by those buildings. The event ordering requires a sophisticated comparator over building start and end markers.

Input Format

buildings = array of [left, right, height]

Output Format

skyline key points as coordinate-height pairs

Constraints

  • 1 <= buildings.length <= 10^4; buildings[i].length == 3; 0 <= left < right <= 2^31 - 1; 0 < height <= 2^31 - 1

Examples

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:

Key points are captured whenever the skyline height changes.

Example 2:

Input:

buildings = [[0,2,3],[2,5,3]]

Output:

[[0,3],[5,0]]

Explanation:

Touching buildings with the same height produce a single plateau.

Loading...
The Skyline Problem