Help: Python solution but time exceeds :(


  • 0
    S
    class Solution(object):
        def getSkyline(self, buildings):
            """
            :type buildings: List[List[int]]
            :rtype: List[List[int]]
            """
            buildings = [[x[0], x[2]] for x in buildings] + [[x[1], -x[2]] for x in buildings]
            buildings = sorted(buildings, key=lambda x: (x[0], -x[1]))
    
            heap = [0]
            prev_max = 0
            res = []
    
            for x in buildings:
                if x[1] > 0:  # rectangle starts
                    heapq.heappush(heap, -x[1])
                else:  # rectangle ends
                    heap.remove(x[1])
                    heapq.heapify(heap)
    
                if heap[0] != prev_max:
                    prev_max = heap[0]
                    res.append([x[0], -heap[0]])
    
            return res
    

    Removal from the heap is O(n) and heapify is O(logn), which should make the overall complexity O(n^2). I've seen other solutions here that are similar. But not sure why mine does not pass.


Log in to reply
 

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