099. Skyline Key Points

Why this mechanism works

Only the tallest active building determines the outline. Sweep every start and end coordinate, pushing starting buildings into a max-oriented heap. Expired buildings may remain below the top harmlessly; remove them when exposed. Process all starts and expirations at a coordinate before emitting one height change.

State and boundaries

heap stores (-height,end) candidates, possibly including hidden expired entries. After cleanup its top is the tallest active building; a zero-height infinite sentinel represents ground.

Protocol

1. Group starts and register every endpoint.
2. Sweep sorted coordinates.
3. Push all buildings starting here.
4. Pop expired heap tops with end<=x.
5. Read the visible height.
6. Emit only if it differs from the previous height.

Visualization

buildings [1,4) height 3; [2,5) height 4
visible: 0 -> 3 at 1 -> 4 at 2 -> 0 at 5
end at 4 is hidden, so no key point

Python implementation

import heapq

def skyline(buildings):
    starts = {}
    for left, right, height in buildings:
        starts.setdefault(left, []).append((-height, right))
        starts.setdefault(right, [])
    heap = [(0, float('inf'))]
    output = []
    previous = 0
    for x in sorted(starts):
        for entry in starts[x]:
            heapq.heappush(heap, entry)
        while heap[0][1] <= x:
            heapq.heappop(heap)
        height = -heap[0][0]
        if height != previous:
            output.append([x, height])
            previous = height
    return output

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L4 skyline: starts = {}
buildings=[(1, 4, 3), (2, 5, 4)]; starts={}

L5 skyline: for left, right, height in buildings:
buildings=[(1, 4, 3), (2, 5, 4)]; starts={}; left=1; right=4; height=3

L6 skyline: starts.setdefault(left, []).append((-height, right))
buildings=[(1, 4, 3), (2, 5, 4)]; starts={1:[(..., ...)]}; left=1; right=4; height=3

L7 skyline: starts.setdefault(right, [])
buildings=[(1, 4, 3), (2, 5, 4)]; starts={1:[(..., ...)], 4:[]}; left=1; right=4; height=3

L5 skyline: for left, right, height in buildings:
buildings=[(1, 4, 3), (2, 5, 4)]; starts={1:[(..., ...)], 4:[]}; left=2; right=5; height=4

L6 skyline: starts.setdefault(left, []).append((-height, right))
buildings=[(1, 4, 3), (2, 5, 4)]; starts={1:[(..., ...)], 4:[], 2:[(..., ...)]}; left=2; right=5; height=4

L7 skyline: starts.setdefault(right, [])
buildings=[(1, 4, 3), (2, 5, 4)]; starts={1:[(..., ...)], 4:[], 2:[(..., ...)], 5:[]}; left=2; right=5; height=4

L8 skyline: heap = [(0, float('inf'))]
buildings=[(1, 4, 3), (2, 5, 4)]; starts={1:[(..., ...)], 4:[], 2:[(..., ...)], 5:[]}; left=2; right=5; height=4; heap=[(0, inf)]

... 17 intermediate state changes omitted ...

L15 skyline: heapq.heappop(heap)
buildings=[(1, 4, 3), (2, 5, 4)]; starts={1:[(..., ...)], 4:[], 2:[(..., ...)], 5:[]}; left=2; right=5; height=4; heap=[(0, inf)]; output=[[1, 3], [2, 4]]; previous=4; x=5; entry=(-4, 5)

L16 skyline: height = -heap[0][0]
buildings=[(1, 4, 3), (2, 5, 4)]; starts={1:[(..., ...)], 4:[], 2:[(..., ...)], 5:[]}; left=2; right=5; height=0; heap=[(0, inf)]; output=[[1, 3], [2, 4]]; previous=4; x=5; entry=(-4, 5)

L18 skyline: output.append([x, height])
buildings=[(1, 4, 3), (2, 5, 4)]; starts={1:[(..., ...)], 4:[], 2:[(..., ...)], 5:[]}; left=2; right=5; height=0; heap=[(0, inf)]; output=[[1, 3], [2, 4], [5, 0]]; previous=4; x=5; entry=(-4, 5)

L19 skyline: previous = height
buildings=[(1, 4, 3), (2, 5, 4)]; starts={1:[(..., ...)], 4:[], 2:[(..., ...)], 5:[]}; left=2; right=5; height=0; heap=[(0, inf)]; output=[[1, 3], [2, 4], [5, 0]]; previous=0; x=5; entry=(-4, 5)

L4 skyline: starts = {}
buildings=[(1, 2, 3), (2, 3, 3)]; starts={}

L5 skyline: for left, right, height in buildings:
buildings=[(1, 2, 3), (2, 3, 3)]; starts={}; left=1; right=2; height=3

L6 skyline: starts.setdefault(left, []).append((-height, right))
buildings=[(1, 2, 3), (2, 3, 3)]; starts={1:[(..., ...)]}; left=1; right=2; height=3

L7 skyline: starts.setdefault(right, [])
buildings=[(1, 2, 3), (2, 3, 3)]; starts={1:[(..., ...)], 2:[]}; left=1; right=2; height=3

L5 skyline: for left, right, height in buildings:
buildings=[(1, 2, 3), (2, 3, 3)]; starts={1:[(..., ...)], 2:[]}; left=2; right=3; height=3

L6 skyline: starts.setdefault(left, []).append((-height, right))
buildings=[(1, 2, 3), (2, 3, 3)]; starts={1:[(..., ...)], 2:[(..., ...)]}; left=2; right=3; height=3

L7 skyline: starts.setdefault(right, [])
buildings=[(1, 2, 3), (2, 3, 3)]; starts={1:[(..., ...)], 2:[(..., ...)], 3:[]}; left=2; right=3; height=3

L8 skyline: heap = [(0, float('inf'))]
buildings=[(1, 2, 3), (2, 3, 3)]; starts={1:[(..., ...)], 2:[(..., ...)], 3:[]}; left=2; right=3; height=3; heap=[(0, inf)]

... 12 intermediate state changes omitted ...

L15 skyline: heapq.heappop(heap)
buildings=[(1, 2, 3), (2, 3, 3)]; starts={1:[(..., ...)], 2:[(..., ...)], 3:[]}; left=2; right=3; height=3; heap=[(0, inf)]; output=[[1, 3]]; previous=3; x=3; entry=(-3, 3)

L16 skyline: height = -heap[0][0]
buildings=[(1, 2, 3), (2, 3, 3)]; starts={1:[(..., ...)], 2:[(..., ...)], 3:[]}; left=2; right=3; height=0; heap=[(0, inf)]; output=[[1, 3]]; previous=3; x=3; entry=(-3, 3)

L18 skyline: output.append([x, height])
buildings=[(1, 2, 3), (2, 3, 3)]; starts={1:[(..., ...)], 2:[(..., ...)], 3:[]}; left=2; right=3; height=0; heap=[(0, inf)]; output=[[1, 3], [3, 0]]; previous=3; x=3; entry=(-3, 3)

L19 skyline: previous = height
buildings=[(1, 2, 3), (2, 3, 3)]; starts={1:[(..., ...)], 2:[(..., ...)], 3:[]}; left=2; right=3; height=0; heap=[(0, inf)]; output=[[1, 3], [3, 0]]; previous=0; x=3; entry=(-3, 3)

Why the solution is correct

Any hidden expired entry cannot affect the maximum until it reaches the top, at which point cleanup removes it. After cleanup the top is therefore the tallest active building. Height is constant between event coordinates, so emitting only changes reconstructs the complete outline without duplicate-coordinate artifacts.

Time and space

O(n log n) time and O(n) space; each building is pushed and popped at most once.

Common mistakes

Emitting after each individual event creates false vertical blips at shared coordinates. Removing only buildings whose end equals x leaves earlier expired heap entries stale.

Reasoning card

Transfer exercise

Integrate consecutive skyline heights times x-distance to compute the area under the visible outline.