Advertisement
kosievdmerwe

218

Sep 29th, 2022
1,002
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.16 KB | None | 0 0
  1. from sortedcontainers import SortedList
  2.  
  3. class Solution:
  4.     def getSkyline(self, buildings: List[List[int]]) -> List[List[int]]:
  5.         events = []  # x, y, add
  6.         for left, right, height in sorted(buildings):
  7.             heappush(events, (left, False, -height))
  8.             heappush(events, (right, True, height))
  9.            
  10.         ans = []
  11.         cur_heights = SortedList()
  12.         last_height = 0
  13.         while events:
  14.             x, nadd, height = heappop(events)
  15.             add = not nadd
  16.             if add:
  17.                 height = -height
  18.            
  19.             if add:
  20.                 if height > last_height:
  21.                     ans.append([x, height])
  22.                     last_height = height
  23.                 cur_heights.add(height)
  24.             else:
  25.                 cur_heights.remove(height)
  26.                 if height == last_height:
  27.                     new_height = 0
  28.                     if cur_heights:
  29.                         new_height = cur_heights[-1]
  30.                     if last_height != new_height:
  31.                         last_height = new_height
  32.                         ans.append([x, new_height])
  33.         return ans
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement