Height of Buildings: Find Visible Skyline Silhouette from a List of Building Rectangles
Question Details
Problem
Given a list of buildings where each building is [left, right, height],
return the skyline silhouette as a list of [x, height] key points. A key point marks where the visible height changes.
python
def get_skyline(buildings: list[list[int]]) -> list[list[int]]:
pass
Example:
buildings = [[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]]
**output** -> [[2,10],[3,15],[7,12],[12,0],[15,10],[20,8],[24,0]]
Approach
Sweep-line + max-heap. At each event point (building start or end), update a max-heap of active heights. Emit a key point whenever the current maximum height changes. O(n log n).
Follow-ups
1. What data structure would you choose for the active-height set if you also need efficient deletions? (Hint: lazy deletion on a heap vs. a sorted multiset.)
2. Two buildings share the same left edge. How do you break ties in your event ordering?
3. Extend to 3D: given box footprints and heights, project the silhouette onto the X-axis.
4. You receive buildings as a stream. How do you output skyline updates incrementally?
Full Details
Problem
Given a list of buildings where each building is [left, right, height],
return the skyline silhouette as a list of [x, height] key points. A key point marks where the visible height changes.
python
def get_skyline(buildings: list[list[int]]) -> list[list[int]]:
pass
Example:
buildings = [[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]]
**output** -> [[2,10],[3,15],[7,12],[12,0],[15,10],[20,8],[24,0]]
Approach
Sweep-line + max-heap. At each event point (building start or end), update a max-heap of active heights. Emit a key point whenever the current maximum height changes. O(n log n).
Follow-ups
1. What data structure would you choose for the active-height set if you also need efficient deletions? (Hint: lazy deletion on a heap vs. a sorted multiset.)
2. Two buildings share the same left edge. How do you break ties in your event ordering?
3. Extend to 3D: given box footprints and heights, project the silhouette onto the X-axis.
4. You receive buildings as a stream. How do you output skyline updates incrementally?
About This Question
This is a reported interview question from a chime interview during the phone round.