The Skyline Problem

The Skyline Problem is a classic sweep-line interview question. Given a set of buildings, you must trace the outline their silhouette makes against the sky — and the elegant solution pairs a left-to-right sweep with a max-heap of live heights.

The slow way first

The brute-force idea: sweep every integer x-coordinate, and at each one loop over all buildings to find the tallest that covers it. That is O(n · W) where W is the coordinate range — far too slow, and it breaks entirely on large coordinates.

The question to ask: the silhouette height only ever changes at a building edge. So I do not need every x — only the critical x-edges (each building's left and right). And at each edge, I want one number fast: the tallest building currently alive. A max-heap answers that in O(log n).

The idea: sweep edges, max-heap the live heights

Collect every building's left and right x into a sorted list of edges. Sweep them in order. As you reach each edge x:

• Push any building whose left edge is x — store its height keyed by its right edge.
• Drop any heap entry whose right edge is already behind you (right ≤ x); it is no longer live.
• Read the tallest live height off the top of the heap. If it differs from the previous tallest, the silhouette just changed — emit a key point [x, tallest].

The key insight: the heap top is the silhouette height. A new point is needed only when that top changes, which keeps the output minimal and correct.

Walk through it

Step through the animation. The pointer x sweeps the sorted edges. The heap line shows live heights keyed by their right edge; tallest live is the heap top. Whenever the tallest changes — 0→10 at x=2, 10→15 at x=3, 15→12 at x=7, 12→0 at x=12 — a key point is appended to the skyline.

Pseudocode

edges = sorted set of every building's left and right x
heap = empty max-heap of (height, right_edge)
prev_tallest = 0
for each x in edges:
    push (height, right) for every building whose left == x
    pop heap entries whose right <= x          # lazily drop dead buildings
    tallest = heap top height, or 0 if empty
    if tallest != prev_tallest:
        emit key point [x, tallest]
        prev_tallest = tallest
return the emitted key points

The Python solution

def get_skyline(buildings):
    events = sorted({b[0] for b in buildings} | {b[1] for b in buildings})
    skyline, heap, prev = [], [], 0
    for x in events:
        for L, R, H in buildings:
            if L == x:
                heapq.heappush(heap, (-H, R))
        while heap and heap[0][1] <= x:
            heapq.heappop(heap)
        cur = -heap[0][0] if heap else 0
        if cur != prev:
            skyline.append([x, cur])
            prev = cur
    return skyline

• events is the sorted set of critical x-edges — every left and right, deduplicated.
• Python has no max-heap, so we push negated heights (-H, R); the smallest negative is the tallest.
• The inner for pushes every building that starts at this x, keyed by its right edge R.
• The while loop is lazy deletion: instead of searching the heap, we drop dead entries from the top whenever their right edge is at or behind x.
• cur is the tallest live height (the heap top), or 0 when nothing is live.
• We emit a key point only when cur differs from prev — that is when the silhouette actually steps up or down.

Complexity

Each building is pushed and popped at most once, and every heap operation is O(log n), so the sweep is O(n log n). The heap holds at most n live buildings, giving O(n) extra space.

When this pattern shows up

Practice