TLE in Python Solution

  • 4

    I came up with the following python solution, which more or less is a translation from jinwu's Java solution:

    Although it works for small test cases, when the test case is extremely large, it hits the TLE. I believe the issue is that whenever we remove an element from the priority queue, we need to re-heapify the entire list in order to maintain its invariant, and it is O(n) to heapify the list.

    Does anyone know how to work around this issue?

    import heapq
    class Solution(object):
        def getSkyline(self, buildings):
            :type buildings: List[List[int]]
            :rtype: List[List[int]]
            points = []
            for b in buildings:
                points.append((b[0], -b[2]))
                points.append((b[1], b[2]))
            points.sort(key=lambda x: (x[0], x[1]))
            # prev stores the current height
            prev = 0
            pq = [0]
            results = []
            for p in points:
                if p[1] < 0:
                    heapq.heappush(pq, p[1])
                    if -p[1] in pq:
                current = -pq[0]
                if prev != current:
                    results.append((p[0], current))
                    prev = current
            return results

  • 4


    if -p[1] in pq:

    can be converted to:

    if -p[1] in pq:
        i = pq.index(-p[1])
        pq[i] = pq[-1]
        if i < len(pq):
            heapq._siftup(pq, i)
            heapq._siftdown(pq, 0, i)

  • 0
    This post is deleted!

  • 0

    removing not from top is very slow in heap which takes O(n) time. Maybe it's not the problem of heapify.

  • 1

    It's weird to call internal functions but it works...

  • 0

    This also works slightly better than above approach. 775ms.

    index = q.index(-i[1])
    while index > 0:
        up = (index + 1) / 2 - 1
        q[index] = q[up]
        index = up

    PS: heapify(q) taks longer time. Because it does some useless work.

Log in to reply

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