95 ms, 12 line Python solution with explanation


  • 1
    D
    import heapq
    
    class Solution(object):
        def getSkyline(self, buildings):
            heap,skyline,i = [],[],0
            crit_pts = sorted([a for b in buildings for a in (b[0],b[1])])
            for pt in crit_pts:
                while heap and heap[0][1] <= pt:
                    heapq.heappop(heap)
                while i < len(buildings) and buildings[i][0] == pt:
                    heapq.heappush(heap,(-buildings[i][2],buildings[i][1]))
                    i += 1
                height = -heap[0][0] if heap else 0
                if not skyline or skyline[-1][1] != height:
                    skyline.append([pt,height])
            return skyline
    

    The idea is to go through the buildings, identify critical points (start and end point of each building), sort them, and go through them. At each critical point, a heap is used to remove any "expired" buildings and to add any buildings if we've arrived at their start. Next, the maximum height is defined by the heap's root height, and that height along with the critical point we're at is appended to the skyline.


Log in to reply
 

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