Last active
May 6, 2022 23:02
-
-
Save ibeauregard/95b4cb55fd77a8bbe34b3d595d9f65b4 to your computer and use it in GitHub Desktop.
The Skyline problem (https://leetcode.com/problems/the-skyline-problem/)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment