progress

~/problems / Heaps / Heaps and priority queues

The Skyline Problem

On a phone? Coding is easier on a laptop: email this problem to yourself . Meanwhile: quiz this topic or fight a boss.

hard ~45 min GoogleBloomberg

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 height 0.
  • A building covers left <= x < right for this purpose: at x = right it 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 - 1 and 1 <= height <= 2^31 - 1.
  • ⭐ Bonus: checking every building at every key x is 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.

Topic: Heaps and priority queues. heapq: top-k, k-way merge, two heaps for a running median.

Read the visual guide
0:00
Ctrl ' run · Ctrl ↵ submit
esc