leetcode(34)优先队列系列题目

218. 天际线问题

用SortedList存边界，每次删除或加入边界判断最高点是否变化

class Solution:
    def getSkyline(self, buildings: List[List[int]]) -> List[List[int]]:
        from sortedcontainers import SortedList
        change = []
        for l, r, h in buildings:
            change.append((l, -h))
            change.append((r, h))
        change.sort()
        pre = 0
        res = []
        s = SortedList([0])
        for i, h in change:
            if h < 0:
                s.add(h)  # 存入左边界
            else:
                s.remove(-h)  # 删除右边界
            cur_mx = -s[0]
            if cur_mx != pre:  # 存入或删除边界后可能发生改变
                pre = cur_mx
                res.append((i, cur_mx))
        return res