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 <= pos[i]: heapq.heappop(heap) while j < N and buildings[j] <= pos[i] < buildings[j]: heapq.heappush(heap, [-buildings[j], buildings[j], buildings[j]]) j += 1 if heap: pos[i] = max(pos[i], -heap) for i in range(n): if not i or pos[i] != pos[i-1]: res.append(pos[i]) return res