12 lines O(nlogn) Python using heap


  • 1

    Based on a beautiful article here. It's obvious to find a key point (x, y) only may exist when x is on the left or right boundaries of a building. Thus we can design an O(n^2) algorithm and then using heap to accelerate it into O(nlogn) one.

    class Solution(object):
        def getSkyline(self, buildings):
            """
            :type buildings: List[List[int]]
            :rtype: List[List[int]]
            """
            res, heap = [], []
            pos = sorted([[x, 0] for l, r, h in buildings for x in (l, r)])
            i, j, n, N = 0, 0, len(pos), len(buildings)
            for i in range(n):
                while heap and heap[0][2] <= pos[i][0]: heapq.heappop(heap)
                while j < N and buildings[j][0] <= pos[i][0] < buildings[j][1]:
                    heapq.heappush(heap, [-buildings[j][2], buildings[j][0], buildings[j][1]])
                    j += 1
                if heap: pos[i][1] = max(pos[i][1], -heap[0][0])
            
            for i in range(n):
                if not i or pos[i][1] != pos[i-1][1]: res.append(pos[i])
            return res
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.