Compute The Overlapping-Load Skyline
Each service deploys over an interval [start, end) and contributes a fixed load level during that span. Overlapping deployments stack; only the maximum active load matters. Produce the silhouette of peak load over time as a list of change points.
Problem
Given buildings where buildings[i] = [left, right, height], return the skyline as a list of 'key points' [x, height] sorted by x. Each key point marks the left endpoint of a horizontal segment in the outer contour; the last point has height 0. Consecutive segments must not have equal heights.
Input
A list of [left, right, height] triples (right is exclusive of the contour beyond it).
Output
A list of [x, height] key points describing the skyline.
Constraints
- 1 ≤ buildings.length ≤ 1e4
- 0 ≤ left < right ≤ 2^31 - 1
- 1 ≤ height ≤ 2^31 - 1
Examples
Example 1
Input
[[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],[19,8],[24,0]]
The contour rises and falls as buildings begin and end.
Example 2
Input
[[0,2,3],[2,5,3]]
Output
[[0,3],[5,0]]
Adjacent equal-height buildings merge into one segment.