# 12 lines O(nlogn) Python using heap

• Based on a beautiful article here. It's obvious to find a `key point (x, y)` only may exist when `x` is on the left or right boundaries of a building. Thus we can design an O(n^2) algorithm and then using heap to accelerate it into O(nlogn) one.

``````class Solution(object):
def getSkyline(self, buildings):
"""
:type buildings: List[List[int]]
:rtype: List[List[int]]
"""
res, heap = [], []
pos = sorted([[x, 0] for l, r, h in buildings for x in (l, r)])
i, j, n, N = 0, 0, len(pos), len(buildings)
for i in range(n):
while heap and heap[0][2] <= pos[i][0]: heapq.heappop(heap)
while j < N and buildings[j][0] <= pos[i][0] < buildings[j][1]:
heapq.heappush(heap, [-buildings[j][2], buildings[j][0], buildings[j][1]])
j += 1
if heap: pos[i][1] = max(pos[i][1], -heap[0][0])

for i in range(n):
if not i or pos[i][1] != pos[i-1][1]: res.append(pos[i])
return res
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.