#!/usr/bin/env python3
# In order to store our current state, we need two pieces of
# sorted information
# 1. Right coordinates (sorted by minimum) of buildings that already ended
# 2. Max height coordinate of active buildings
# And we must be able to remove a building from the max-height list,
# after finding it ended in the right coordinates list
# I haven't done any performance tests against the more standard solution,
# however it ought to have similar runtime: O(n log n) since each building
# must be added and removed from two heaps, and each heap add and remove
# takes (log n) time.
# space usage for this solution is O(n).
# global indices into a building-list: right, left, height, and height-heap-index
R = 0
L = 1
H = 2
Hix = 3
from heapq import heappush, heappop
from ixheapq import Ixheapq
class HeightMaxHeap(Ixheapq):
def store_pos (self, item, pos):
item[Hix] = pos
def less_than (self, a, b):
return a[H] > b[H]
#def height_less (a, b):
#return a[H] < b[H]
Show_Push = True
Show_Remove = True
def finish_skyline (skyline, r_list, h_list, pass_left = None):
# when we arrive at a left coordinate, pop off the right coords less
# than that left coord, completing the skyline as we go.
ended_bldg = None if r_list == [] else r_list[0]
while (ended_bldg is not None
and (pass_left == None or ended_bldg[R] < pass_left)):
heappop(r_list) # ended_bldg is already assigned
#print ('remove', ended_bldg)
h_list.remove (ended_bldg[Hix], Show_Remove)
#print ('after rmv:', h_list.heap)
prev_high = ended_bldg[H]
highest_bldg = h_list.peek()
if highest_bldg is not None:
cur_high = highest_bldg[H]
else:
cur_high = 0
if cur_high < prev_high:
skyline.append ([ended_bldg[R], cur_high])
ended_bldg = None if r_list == [] else r_list[0]
def getSkyline (buildings):
if buildings == []:
return []
r_list = [] # construct bldg list so as to be sorted by right coordinate
h_list = HeightMaxHeap(store_pos_key = Hix)
cur_height = 0
# start the skyline:
skyline = []
for left, width, height in buildings:
right = left+width
# complete the skyline up to this left coord
finish_skyline (skyline, r_list, h_list, left)
# check the highest building before adding a new one,
# to see if this building changes the skyline at this point
highest_bldg = h_list.peek()
if highest_bldg is not None:
prev_high = highest_bldg[H]
else:
prev_high = 0
if height > prev_high:
skyline.append ([left, height])
# add this building to the right-list and height-list
bldg = [right, left, height, -1]
# bldg = {'L': left, 'R': right, 'H': height, 'h_ix': -1}
heappush (r_list, bldg)
h_list.push (bldg, Show_Push)
#print ('after add:', h_list.heap)
# after adding all buildings, finish the skyline
finish_skyline (skyline, r_list, h_list, None)
return skyline