Outline of the Skyline
Each building is [left, right, height]: a rectangle that stands on the ground from x = left to x = right. Seen from far away, the buildings merge into one outline.
Describe the outline from left to right as a list of points [x, height]: one point for every x where the height of the outline changes, with the height it changes to. Where the outline drops to the ground the height is 0, so the last point always has height 0.
Example 1
The outline rises to 3 at x = 1 and to 6 at x = 2, falls back to 3 at x = 4 and to the ground at x = 5. The last building stands alone from 7 to 9.
Example 2
The two buildings touch and are equally tall, so nothing changes at x = 2.
Constraints
1 <= len(buildings) <= 400 <= left < right <= 10**61 <= height <= 10**4
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.
More Sorting and searching problems
- Shorten the Longest GapHard
- Two Teams of Equal SizeHard
- Height CheckerBeginner
- Kth Largest ElementBeginner
- Kth Smallest Distinct ValueBeginner
- Maximum Product of Two ElementsBeginner
- Median of the ListBeginner
- Names in OrderBeginner