218. The Skyline Problem (Hard) - TengnanYao/daily_leetcode GitHub Wiki

class Solution(object):
    def getSkyline(self, buildings):
        """
        :type buildings: List[List[int]]
        :rtype: List[List[int]]
        """
        xs = set()
        for building in buildings:
            xs.add(building[0])
            xs.add(building[1])
        xs = sorted(list(xs))
        
        result = []
        heap = []
        h = 0
        i = 0
        for x in xs:
            while heap and heap[0][1] <= x:
                heapq.heappop(heap)
            while i < len(buildings):
                x1, x2, y = buildings[i]
                if x1 > x: 
                    break
                heapq.heappush(heap, (-y, x2))
                i += 1
            if heap:
                y = -heap[0][0]
                if y != h:
                    result.append([x, y])
                    h = y
            else:
                result.append([x, 0])
        return result