from heapq import heappush, heappop
class Solution:
# time O(NlgN) since 1.sort 2. heap push pop ops cost lgN each time. space O(N) to maintain heap and events
def getSkyline(self, buildings: List[List[int]]) -> List[List[int]]:
events_s = [(L,-H, R) for L,R,H in buildings]
# remove same endpoint events
events_e = list({(R,0,0) for _,R,_ in buildings})
events = sorted(events_s+ events_e)
# initialize start end scale
#@res: [x,h] key point where x stands for valid s_position the building is highest at h
#@ hp: [h,R]: save different height h at e_position R
res, hp = [[0,0]], [(0,float('inf'))]
# loop through all start,end events
for L, negH, R in events:
# remove all the invalid heights when s_position is at L
# also remove posible height candidate when L,H, R is actually (R,0,0)
while L >= hp[0][1]:
heappop(hp)
# make sure it's s_position
if negH:
heappush(hp,(negH,R))
# append when height is different
if -hp[0][0] != res[-1][1]:
res.append([L,-hp[0][0]])
#???? how can you make sure L is the same/valid when you append highest event from hp? since hp store events that ends at that height??
# answer: since events are sorted by 1. L 2. height; so each time a new L comes in, after invalid height with expired R is removed from hp, no matter whether its (h,R) is pushed into hq, we can make sure max height at L is valid
return res[1:]
#################################################################
class Solution:
def getSkyline(self, buildings: List[List[int]]) -> List[List[int]]:
"""
1. seperate left pos, right pos; creat start events and end events(assign neg height to left, and 0 height to right)
2. sort by pos
3. initialize heap and res
4. loop all (start end combined) events heap,
4.1 remove invalid(pos less than start pos)
4.2 add valid height(non-zero) into hp
4.3 add new point into res when last res height point is diffrent from heap's largest height
5. return res except index 0 's
"""
starts = [(l,-h,r) for l,r,h in buildings]
ends = [(r,0,float('inf')) for l,r,h in buildings]
events = sorted(starts + ends)
pq,res = [[0,float('inf')]],[[0,0]]
for l, negH, r in events:
while pq[0][1] <= l: # [l,r)
heappop(pq)
# filter out end point
if negH:
heappush(pq,[negH,r])
# if height changes, update result new height at t = left_time
if res[-1][1] != -pq[0][0]:
res.append([l,-pq[0][0]])
return res[1:]