O(n log n) time, O(n) space. But it's likely even faster than that. The log(n) only comes from:
sortedcall: 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).
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 = , Counter() 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]: heappop(heights) height = -heights if not skyline or height != skyline[-1]: skyline += [[x, height]] return skyline