Skyline Outline

Problem

Given buildings as [left, right, height], return the skyline as a list of [x, height] key points where the silhouette changes, including drops to height 0.

Sweep the x coordinates with a max-heap of active building heights, discarding buildings whose right edge has passed. Emit a key point only when the current maximum height differs from the last recorded height.

Hint

Storing negative heights lets a min-heap act as a max-heap.

Test cases

case 1

in: [[[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]]]

expected: [[2,10],[3,15],[7,12],[12,0],[15,10],[20,8],[24,0]]

case 2

in: [[[0,2,3],[2,4,3],[4,6,3]]]

expected: [[0,3],[6,0]]

case 3

in: [[]]

expected: []

case 4

in: [[[1,2,1]]]

expected: [[1,1],[2,0]]

case 5

in: [[[0,1,2],[1,2,2]]]

expected: [[0,2],[2,0]]

Starter codePython

def skyline_outline(buildings):
    # Your code here
    pass

5 test cases · run your code against them in the editor