[LeetCode][Python3] 218. The Skyline Problem

Problem :

https://leetcode.com/problems/the-skyline-problem/

My Solution :

from bisect import insort, bisect_left

class Solution:

def getSkyline(self, buildings):

if not buildings:

return []

height = set()

for building in buildings:

L, R, H = building

height.add((L, -H))

height.add((R, H))

ret, queue = [], [0]

before = queue[-1]

for P, H in sorted(height):

if H < 0:

insort(queue, -H)

else:

queue.pop(bisect_left(queue, H))

if queue[-1] != before:

ret.append([P, queue[-1]])

before = queue[-1]

return ret

Comment :

Left에서는 높이를 heapq에 push하고, Right에서는 높이를 heapq에서 remove 한다. Left 높이를 음수로 처리하면 정렬시 양수보다 우선순위를 가지고 (같은 점에서 push가 remove보다 먼저 일어나게 되고) Left, Right 여부를 음/양으로 구분할 수 있어 유리하다. heapq를 쓰나 bisect.insort를 쓰나 속도는 별 차이 없었다.