***218. The Skyline Problem []
2019-10-10 本文已影响0人
一个想当大佬的菜鸡
218. The Skyline Problem
import heapq
class Solution(object):
def getSkyline(self, buildings):
"""
:type buildings: List[List[int]]
:rtype: List[List[int]]
"""
points = []
delete = {}
for x, y, h in buildings:
points.append([x, -h])
points.append([y, h])
points.sort(key=lambda x:(x[0], x[1]))
max_value = 0
heap = []
heapq.heappush(heap, max_value)
res = []
for point in points:
if point[1] < 0:
heapq.heappush(heap, point[1])
if -point[1] > max_value:
max_value = -point[1]
res.append([point[0], max_value])
else:
tmp = -point[1]
if tmp == heap[0]:
heapq.heappop(heap)
while heap[0] in delete:
value = heap[0]
heapq.heappop(heap)
delete[value] -= 1
if delete[value] == 0:
del delete[value]
if -heap[0] < max_value:
max_value = -heap[0]
res.append([point[0], max_value])
else:
delete[tmp] = delete.get(tmp, 0) + 1
return res