City Skyline

From far away, the buildings of a city blend into one outline. Each building is a rectangle standing on the ground: (left, right, height) covers x from left to right and is height tall.

Write skyline(buildings) that returns the outline as a list of key points, (x, height) tuples sorted by x. A key point marks where the outline's height changes, and height is the outline's height from x until the next key point. Where no building stands the height is 0, so the last key point always has height 0.

Two key points in a row never have the same height: where the outline does not change (for example where two buildings of the same height touch), there is no key point.

Examples

skyline([(1, 5, 3), (2, 4, 6), (6, 8, 2)])
# returns [(1, 3), (2, 6), (4, 3), (5, 0), (6, 2), (8, 0)]

skyline([(0, 2, 4), (2, 5, 4)])
# returns [(0, 4), (5, 0)]

skyline([])
# returns []

In the first example the tall building covers x from 2 to 4, so the outline rises to 6 there and falls back to 3 until the first building ends at 5.

Constraints

• 0 <= len(buildings) <= 50,000, in any order
• 0 <= left < right <= 10^9 and 1 <= height <= 10^9
• Buildings can overlap, stand inside each other or share edges. Checking every building at every edge is too slow for 50,000 buildings.