The Skyline Problem: Explaining the Sweep Line and Heap in a Coding Interview

The skyline problem is a classic "hard" question because it combines three ideas at once: turning shapes into events, sweeping left to right, and keeping the current maximum height in a heap. If you can narrate those three steps clearly, the code almost writes itself.

1. Turn buildings into events

Each building [left, right, height] produces a start event at left and an end event at right. A common trick is to store start events with a negative height so that sorting by (x, height) processes taller starts first and avoids duplicate key points at the same x.

2. Sweep with a max-heap and lazy deletion

import heapq

def get_skyline(buildings):
    events = []
    for l, r, h in buildings:
        events.append((l, -h, r))   # start: negative height, remember end
        events.append((r, 0, 0))    # end marker
    events.sort()

    result = []
    heap = [(0, float('inf'))]      # (negative height, end x)
    for x, neg_h, r in events:
        if neg_h:
            heapq.heappush(heap, (neg_h, r))
        while heap[0][1] <= x:      # lazily drop buildings that ended
            heapq.heappop(heap)
        height = -heap[0][0]
        if not result or result[-1][1] != height:
            result.append([x, height])
    return result

3. What to say while you code

4. Test cases worth mentioning

Hard sweep-line problems are easier when you practice explaining them live. If you want real-time support during practice rounds, take a look at Linkjob, an AI assistant for technical interviews.

Disclosure: I work on Linkjob AI.