The skyline problem: outline of overlapping buildings

Buildings stand on flat ground, each given as [left, right, height] with left < right. They may overlap. Return the skyline they form seen from far away: the list of key points [x, height] where the outline's height changes.

Interface

Unless you agree on a different interface with the interviewer, assume:

• skyline(buildings: list[list[int]]) -> list[list[int]] — key points sorted by x. No two consecutive points have the same height, the first point has a positive height, and the last has height 0. When several buildings start or end at the same x, emit one point with the final height there.

Example

skyline([[2, 9, 10], [3, 7, 15], [5, 12, 12]])  ->  [[2, 10], [3, 15], [7, 12], [12, 0]]
skyline([[0, 2, 3], [2, 5, 3]])                 ->  [[0, 3], [5, 0]]          # same height across a shared edge: no point at 2
skyline([[1, 3, 4], [3, 6, 2]])                 ->  [[1, 4], [3, 2], [6, 0]]
skyline([[1, 5, 3], [1, 5, 7]])                 ->  [[1, 7], [5, 0]]          # same start: only the taller one shows

Constraints

• 1 <= n <= 10^4.
• 0 <= left < right <= 10^9, 1 <= height <= 10^9.

Clarifying questions

• Is the input sorted by left?
• When one building ends exactly where another of the same height starts, should there be a point there? (No.)
• Are coordinates integers, and can they be large enough that a per-x array is impossible?
• Do you want the points as pairs or as two arrays?

What a strong answer covers

• Sweep line: turn each building into a start and an end event, sort by x, and keep a max-heap of active heights.
• Lazy deletion: store (height, right) in the heap and pop entries whose right <= x before reading the top, instead of removing from the middle of a heap.
• Process all events at one x before emitting, then emit only when the max height changed. That handles shared edges and equal starts.
• O(n log n) time, O(n) space. A divide-and-conquer merge of two skylines is an equally good alternative; know how its merge step works.
• Tests: one building, nested buildings, touching buildings of equal and different heights, identical buildings.

Follow-ups

• Buildings arrive one at a time and the skyline must stay current.
• Return the total area under the skyline.
• Coordinates are small (up to 10^5). Is a segment tree or a direct array simpler?