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, -b)) points.append((b, b)) points.sort(key=lambda x: (x, x)) # prev stores the current height prev = 0 pq =  results =  for p in points: if p < 0: heapq.heappush(pq, p) else: if -p in pq: pq.remove(-p) heapq.heapify(pq) current = -pq if prev != current: results.append((p, current)) prev = current return results
if -p in pq: pq.remove(-p) heapq.heapify(pq)
can be converted to:
if -p in pq: i = pq.index(-p) pq[i] = pq[-1] pq.pop() if i < len(pq): heapq._siftup(pq, i) heapq._siftdown(pq, 0, i)
removing not from top is very slow in heap which takes O(n) time. Maybe it's not the problem of heapify.
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.