Python O(n)


  • 0

    This isn't the most concise way to do it, but it uses no extra space besides the output array.

        def getSkyline(self, buildings):
            if not buildings:
                return []
            last = heapq.heappop(buildings)
            skyline = []
            S, E, H = 0, 1, 2
            while buildings:
                building = heapq.heappop(buildings)
                
                if building[S] >= last[E]: # no overlap
                    if last[H] == building[H]:
                        last[E] = building[E]
                    else:
                        skyline.append([last[S], last[H]])
                        if building[S] > last[E]:
                            skyline.append([last[E], 0])
                        last = building
                    
                elif building[H] == last[H]: # same height
                    last[E] = max(last[E], building[E])
                    
                elif building[H] > last[H]:
                    if building[E] < last[E]:         
                        heapq.heappush(buildings, [building[E], last[E], last[H]])
                    if building[S] > last[S]:
                        skyline.append([last[S], last[H]])
                        last = building
                    else:
                        last[E], last[H] = building[E], building[H]
                        
                elif building[E] > last[E]: # less than ->  partition only when building is stretched further out
                    building[S] = last[E]
                    heapq.heappush(buildings, building)
            
            return skyline + [[last[S], last[H]], [last[E], 0]]
    

Log in to reply
 

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