240. City Outline
You are drawing the outline of a city seen from far away. Every building is a rectangle standing on flat ground, given as buildings[i] = [left, right, height]: it occupies the horizontal range from left to right (the wall at right is already outside the building) and rises to height. Buildings may overlap and may be given in any order.
The outline is described by key points: a key point [x, h] is placed at every position x where the height of the outline changes, and h is the new height starting at x. List the key points sorted by x. The last key point always has height 0 (the end of the city), there are never two consecutive key points with the same height, and flat stretches are not marked. If there are no buildings the answer is an empty list.
Buildings that are empty (left >= right) or have no height (height <= 0) are ignored.
Example 1
- Input:
- buildings = [[1,4,3],[2,6,5]]
- Output:
- [[1,3],[2,5],[6,0]]
- Explanation:
From x=1 the height is 3; at x=2 the taller building (5) takes over; at x=6 everything ends. Outline: [1,3], [2,5], [6,0]. The wall at x=4 is hidden behind the taller building.
Example 2
- Input:
- buildings = [[0,3,4],[3,6,4]]
- Output:
- [[0,4],[6,0]]
- Explanation:
Two equal-height buildings touch at x=3, so the height does not change there and no key point is placed: [0,4], [6,0].
Example 3
- Input:
- buildings = [[2,3,7],[1,10,2],[4,8,6]]
- Output:
- [[1,2],[2,7],[3,2],[4,6],[8,2],[10,0]]
- Explanation:
A low wide building (2) with a tall narrow one in front and a mid-height one later. Outline: [1,2], [2,7], [3,2], [4,6], [8,2], [10,0].
Example 4
- Input:
- buildings = [[5,5,9],[1,2,4]]
- Output:
- [[1,4],[2,0]]
- Explanation:
The first entry is empty (left == right) and is ignored, leaving [1,4], [2,0].
Constraints
0 ≤ buildings.length ≤ 105
0 ≤ left < right ≤ 109, 1 ≤ height ≤ 109 for valid buildings
Robustness: entries with left ≥ right or height ≤ 0 are skipped.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 2,400 msC++ 600 msJava 1,200 msJavaScript 1,200 msTypeScript 1,200 ms
Expected complexity
- Time
- O(n log n)
- Space
- O(n)