You are given a list of rectangular buildings in a 2D city skyline.
Each building is represented by three integers [L, R, H]:
L
: the x-coordinate of the left edge of the building,
R
: the x-coordinate of the right edge of the building (
L < R
),
H
: the height of the building.
All buildings stand on a flat horizontal line (y = 0) and extend vertically up to height H. Buildings may overlap in the x-dimension.
Your task is to compute the skyline formed by these buildings, as seen from a distance. The skyline should be represented as a list of key points [x, height] that describe the outer contour of the union of all buildings.
A key point is a point where the height of the skyline changes. The output list must satisfy all of the following:
x
.
n
— the number of buildings.
n
buildings, where each building is given as a triple
[L, R, H]
of integers.
You may assume:
1 <= n <= 10^4
0 <= L < R <= 10^9
1 <= H <= 10^9
Return a list of key points representing the skyline. Each key point is a pair [x, height] (or a 2-element array/tuple) of integers.
Input:
n = 3
[[2, 9, 10], [3, 7, 15], [5, 12, 12]]
One valid output:
[[2, 10], [3, 15], [7, 12], [12, 0]]
Explanation (informal):
Design an algorithm to compute the skyline key points for the given buildings.