Compute city skyline outline
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
You are given a list of rectangular buildings in a 2D city skyline.
Each building is represented by three integers `[L, R, H]`:
- `L`: the x-coordinate of the left edge of the building,
- `R`: the x-coordinate of the right edge of the building (`L < R`),
- `H`: the height of the building.
All buildings stand on a flat horizontal line (y = 0) and extend vertically up to height `H`. Buildings may overlap in the x-dimension.
Your task is to compute the *skyline* formed by these buildings, as seen from a distance. The skyline should be represented as a list of **key points** `[x, height]` that describe the outer contour of the union of all buildings.
A **key point** is a point where the height of the skyline changes. The output list must satisfy all of the following:
1. The list is sorted by increasing `x`.
2. No two consecutive points have the same height (i.e., the height must change at each key point).
3. The first point has a height greater than 0.
4. The last point has height 0, marking the end of the skyline.
### Input
- An integer `n` — the number of buildings.
- A list of `n` buildings, where each building is given as a triple `[L, R, H]` of integers.
You may assume:
- `1 <= n <= 10^4`
- `0 <= L < R <= 10^9`
- `1 <= H <= 10^9`
### Output
Return a list of key points representing the skyline. Each key point is a pair `[x, height]` (or a 2-element array/tuple) of integers.
### Example
Input:
- `n = 3`
- buildings = `[[2, 9, 10], [3, 7, 15], [5, 12, 12]]`
One valid output:
- `[[2, 10], [3, 15], [7, 12], [12, 0]]`
Explanation (informal):
- From x = 2 to 3, the highest building has height 10.
- From x = 3 to 7, the highest building has height 15.
- From x = 7 to 12, the remaining highest building has height 12.
- After x = 12, there are no buildings, so the height drops to 0.
Design an algorithm to compute the skyline key points for the given buildings.
Quick Answer: This question evaluates a candidate's understanding of interval processing and skyline/contour computation within computational geometry, focusing on reasoning about overlapping ranges and height aggregation.
You are given a list of rectangular buildings in a 2D city skyline. Each building is represented by three integers `[L, R, H]` where `L` is the x-coordinate of the left edge, `R` the x-coordinate of the right edge (`L < R`), and `H` the height. All buildings stand on the line y = 0 and may overlap in the x-dimension.
Compute the *skyline* — the outer contour of the union of all buildings — as a list of **key points** `[x, height]`, where each key point marks a position at which the skyline height changes.
The output must satisfy:
1. Sorted by increasing `x`.
2. No two consecutive points share the same height.
3. The first point has height > 0.
4. The last point has height 0, marking the end of the skyline.
**Input:** an integer `n` (number of buildings) and a list of `n` triples `[L, R, H]`.
**Output:** the list of key points `[x, height]`.
**Constraints:** `1 <= n <= 10^4`, `0 <= L < R <= 10^9`, `1 <= H <= 10^9`.
Example: buildings `[[2,9,10],[3,7,15],[5,12,12]]` -> `[[2,10],[3,15],[7,12],[12,0]]`.
Constraints
- 1 <= n <= 10^4
- 0 <= L < R <= 10^9
- 1 <= H <= 10^9
- Each building is a triple [L, R, H] of integers.
- Output must be sorted by x, with no two consecutive equal heights, first height > 0, last height = 0.
Examples
Input: (3, [[2, 9, 10], [3, 7, 15], [5, 12, 12]])
Expected Output: [[2, 10], [3, 15], [7, 12], [12, 0]]
Explanation: The prompt example: height 10 from x=2, rises to 15 at x=3, drops to 12 at x=7 once the tallest ends, then to 0 at x=12.
Input: (1, [[0, 2, 3]])
Expected Output: [[0, 3], [2, 0]]
Explanation: A single building: height 3 from x=0 to x=2, then ground.
Hints
- Think of each building as two events: a 'start' at x = L (height rises) and an 'end' at x = R (height may fall). Sort all events by x.
- At any x, the skyline height equals the tallest building currently spanning that x. A max-heap of active building heights gives this in O(log n).
- Use lazy deletion: instead of removing a building's height when it ends, store its right edge with it in the heap and pop entries whose end <= current x before reading the top.
- Emit a key point only when the current max height differs from the last emitted height. When several events share the same x, collapse them so only the final height at that x is recorded.