The skyline

Seen from far away, a row of buildings makes one outline against the sky. Each building is a rectangle standing on the ground, given as (left, right, height): it covers the x values from left up to, but not including, right. Return the outline as a list of key points (x, h): at x the outline’s height changes to h. Between buildings the height is 0.

skyline([(2, 9, 10), (3, 7, 15), (5, 12, 12),
         (15, 20, 10), (19, 24, 8)])
# [(2, 10), (3, 15), (7, 12), (12, 0),
#  (15, 10), (20, 8), (24, 0)]

• The points are sorted by x, and there is exactly one point for each x where the height changes.
• Two neighbouring points never have the same height: if the height does not change at some x, there is no point there.
• The last point has height 0. No buildings give [].

Points may be tuples or lists. All numbers are whole numbers, left < right, and every height is at least 1.

Limits

• Up to 50,000 buildings, in any order. Aim for O(n log n): divide and conquer, as lesson 2’s first worked example describes.