```
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.