#249HardSweep Line· Sweep with a Max-Heap and Lazy Deletion

City Skyline Outline

A city planner wants the silhouette of a row of rectangular buildings seen from far away. Every building is described by `[left, right, height]`: it occupies the horizontal range from `left` to `right` (the right edge is exclusive) and rises to `height` above flat ground at height 0. Buildings may overlap, touch or be nested. The silhouette is a list of **key points** `[x, height]`, sorted by `x`. A key point marks the place where the outline's height changes: it is the left end of a horizontal segment, and `height` is the height of that segment, which extends to the next key point. The last key point is where the last building ends and always has height 0. The list must not contain two consecutive key points with the same height. Return the key points of the silhouette. The result is empty when there are no buildings.

Input format

`buildings`: an array of triples `[left, right, height]` in arbitrary order.

Output format

An array of key points `[x, height]` in increasing order of `x`.

Examples

Input: buildings = [[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], [20, 8], [24, 0]]

The outline climbs to 10 at x=2, to 15 at x=3, drops to 12 at x=7 when the tall building ends, to 0 at x=12, then rises to 10 at x=15, falls to 8 at x=20 and reaches 0 at x=24.

Input: buildings = [[0, 2, 3], [2, 5, 3]]

Output: [[0, 3], [5, 0]]

The buildings touch and have the same height, so there is no change at x=2 and the outline is one flat segment from 0 to 5.

Input: buildings = []

Output: []

No buildings, no key points.

Constraints

0 <= buildings.length <= 10^4
0 <= left < right <= 2^31 - 1
1 <= height <= 2^31 - 1

#sweep-line
#heap
#lazy-deletion
#divide-and-conquer
#geometry