***218. The Skyline Problem []

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