The Skyline Problem

Hard

You are given buildings where buildings[i] = [left, right, height] describes a rectangle standing on a flat ground line.

Return the skyline as a list of key points [x, height], sorted by x. A key point is the left endpoint of a horizontal segment of the outline. The last point always has height 0, marking where the skyline ends.

There must be no consecutive points of equal height — merge those segments.

Example 1

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]]

Example 2

Input:  buildings = [[0,2,3],[2,5,3]]
Output: [[0,3],[5,0]]
Explanation: The two buildings touch and are the same height, so the outline is one segment.

Constraints

• 1 <= buildings.length <= 10^4
• 0 <= left < right <= 2^31 - 1
• 1 <= height <= 2^31 - 1
• buildings is sorted by left ascending