Help: Python solution but time exceeds :(

  • 0
    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
                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.