218. The Skyline Problem

[OverflowCat]

from heapq import *

class Solution:
    def getSkyline(self, buildings: List[List[int]]) -> List[List[int]]:
        curr = [] # (ini, height)
        skyline = []
        for b in buildings:
            flag = True
            while curr and curr[0][2] <= b[1]:
                d = heappop(curr)
                if flag:
                    skyline.append([d[2], d[0]])
                    flag = False
            h = curr[0][0] if curr else 0
            skyline.append([b[0], h])
            if len(curr) == 0 or b[2] > curr[0][0]:
                skyline.append([b[0], b[2]])
            heappush(curr, (b[2], b[0], b[1]))
            skyline.append([heappop(curr)[2], 0])
        ys = defaultdict(set)
        for x in skyline:
            ys[x[0]].add(x[1])
        l = [(x, min(y), max(y)) for x, y in ys.items()]
        skyline = []
        for i in range(len(l) - 1):
            skyline.append([l[i][0], l[i][1]])
            skyline.append([l[i][0], l[i][2]])

        return [x for x in skyline if x is not None]

[OverflowCat]

这样做无法判断进出

from heapq import *

class Solution:
    def getSkyline(self, buildings: List[List[int]]) -> List[List[int]]:
        dots = set()
        for b in buildings:
            dots.add((b[0], b[2], True))
            dots.add((b[1], b[2], False))
            dots.add((b[0], 0))
            dots.add((b[1], 0))
        dots = sorted(list(dots), key=lambda x: x[0])
        return dots