# TLE in Python Solution

• I came up with the following python solution, which more or less is a translation from jinwu's Java solution:
https://leetcode.com/discuss/54201/short-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])
else:
if -p[1] in pq:
pq.remove(-p[1])
heapq.heapify(pq)

current = -pq[0]
if prev != current:
results.append((p[0], current))
prev = current
return results``````

• ``````if -p[1] in pq:
pq.remove(-p[1])
heapq.heapify(pq)
``````

can be converted to:

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

• This post is deleted!

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

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

• 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
heapq.heappop(q)
``````

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

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