O(n log n) time, O(n) space. But it's likely even faster than that. The log(n) only comes from:

- The
`sorted`

call: Python's dictionary keys can be largely sorted already (depends on the input). And Python uses Timsort, which can detect that and take advantage of it. - Pushing to and popping from the heap. This is not log(n) but only log(current size of the heap).

The code:

```
from heapq import *
from collections import *
class Solution:
def getSkyline(self, buildings):
changes = defaultdict(list)
for l, r, h in buildings:
changes[l] += [-h]
changes[r] += [h]
heights, height_ctr = [0], Counter([0])
skyline = []
for x, changes in sorted(changes.items()):
for h in changes:
if h < 0:
heappush(heights, h)
height_ctr[h] += 1
else:
height_ctr[-h] -= 1
while not height_ctr[heights[0]]:
heappop(heights)
height = -heights[0]
if not skyline or height != skyline[-1][1]:
skyline += [[x, height]]
return skyline
```