218 The Skyline Problem

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

solution

• 使用优先队列储存每个建筑物的高度和右端

时间复杂度：O() 空间复杂度：O()

• tree map

• 扫描线

class Solution:
    def getSkyline(self, buildings: List[List[int]]) -> List[List[int]]:
        if not buildings:
            return []
        
        events = []

        for left, right, h in buildings:
            events.append((left, -h, right))  # start point of building
            events.append((right, 0, 0))  # end point of building
        
        events.sort()
        res = [[0, 0]]
        hp = [(0, float('inf'))]  # 结果存的就是高度，右边界

        for pos, h, r in events:
            while hp[0][1] <= pos:  # 本身已经按高度排序，如果右边比上一个小
                heapq.heappop(hp)
            
            if h != 0:
                heapq.heappush(hp, (h, r))
            
            if res[-1][1] != -hp[0][0]:
                res.append([pos, -hp[0][0]])
        return res[1:]