The Skyline problem (https://leetcode.com/problems/the-skyline-problem/)

skyline.py

from itertools import chain
from collections import namedtuple
from heapq import heappop, heappush
# The heapq module maintains a min-heap invariant, so we have to use
# the negative of the buildings' height because we'd like a max-heap
Building = namedtuple('Building', ['neg_height', 'end'])
Line = namedtuple('Line', ['start', 'height'])

# buildings[i] = [left_i, right_i, height_i]
def get_skyline(buildings):
    events = sorted(chain.from_iterable(
        ((start, -height, end), (end, 0, None)) for start, end, height in buildings
    ))

    lines = []
    live_buildings = [Building(neg_height=0, end=float('inf'))]
    def pop_past_buildings():
        while live_buildings[0].end <= start:
            heappop(live_buildings)
    def push_building():
        if neg_height:
            heappush(live_buildings, Building(neg_height=neg_height, end=end))
    def update_lines():
        if not lines or lines[-1].height != -live_buildings[0].neg_height:
            lines.append(Line(start=start, height=-live_buildings[0].neg_height))
    for start, neg_height, end in events:
        pop_past_buildings()
        push_building()
        update_lines()
    return lines