A poster shop prints city skylines as flat silhouettes. Each building is a rectangle standing on flat ground: [left, right, height] covers every x from left to right and rises to height. Buildings may overlap, touch or stand apart. The silhouette is the outline you see from far away: at each x, its height is the height of the tallest building covering that x, or 0 (the ground) if none does.
Write get_skyline(buildings) -> list[list[int]] that describes the silhouette as a list of key points [x, h]: at x, the outline changes to height h and stays there until the next key point.
- Key points are sorted by
x. - Two neighbouring key points never have the same height: if the outline doesn't change, there is no key point.
- Where the outline drops to the ground between buildings, there is a key point with height
0. The last key point is where the last building ends, with height0. - A building covers
left <= x < rightfor this purpose: atx = rightit no longer counts.
get_skyline([[1, 6, 4], [3, 9, 7], [4, 5, 9], [11, 14, 3]])
# [[1, 4], [3, 7], [4, 9], [5, 7], [9, 0], [11, 3], [14, 0]]
get_skyline([[2, 4, 5], [4, 8, 5]])
# [[2, 5], [8, 0]] (same height, touching: one flat roof, no point at 4)
get_skyline([[1, 10, 8], [2, 5, 3]])
# [[1, 8], [10, 0]] (the short building is hidden)
In the first example the tallest building [4, 5, 9] pokes up above [3, 9, 7], which shows again from 5 to 9. Nothing stands between 9 and 11, so the outline is at the ground there.
Constraints:
1 <= len(buildings) <= 10^5, in no particular order.0 <= left < right <= 2^31 - 1and1 <= height <= 2^31 - 1.- ⭐ Bonus: checking every building at every key
xis O(n²) and still passes; a speed test with 100,000 buildings earns a star in O(n log n).
Show hint
Sweep from left to right over the x values where some building starts or ends. At each one you need the tallest building still standing there. A max-heap gives you the tallest, and a building that has ended only gets in the way once it is at the top.