skyline.py 文件源码

def get_skyline(LRH):
    """
    Wortst Time Complexity: O(NlogN)
    :type buildings: List[List[int]]
    :rtype: List[List[int]]
    """
    skyline, live = [], []
    i, n = 0, len(LRH)
    while i < n or live:
        if not live or i < n and LRH[i][0] <= -live[0][1]:
            x = LRH[i][0]
            while i < n and LRH[i][0] == x:
                heapq.heappush(live, (-LRH[i][2], -LRH[i][1]))
                i += 1
        else:
            x = -live[0][1]
            while live and -live[0][1] <= x:
                heapq.heappop(live)
        height = len(live) and -live[0][0]
        if not skyline or height != skyline[-1][1]:
            skyline += [x, height],
    return skyline