1from heapq import heappush, heappop
2from collections import namedtuple
3
4Point = namedtuple("Point", "y x1")
5ResPoint = namedtuple("ResPoint", "x y")
6
7
8class Solution(object):
9 def getSkyline(self, B):
10 scans = sorted(
11 [(x0, -y, x1) for x0, x1, y in B] + [(x1, 0, 0) for _, x1, _ in B]
12 )
13
14 res = [ResPoint(x=0, y=0)]
15 live = [Point(0, float("inf"))]
16 for scan_x0, scan_y, scan_x1 in scans:
17 while live[0].x1 <= scan_x0:
18 heappop(live)
19 if scan_y:
20 heappush(live, Point(scan_y, scan_x1))
21 if res[-1].y != -live[0].y:
22 res += [ResPoint(scan_x0, -live[0].y)]
23 return res[1:]
24
25
26print(Solution().getSkyline([[2, 9, 10], [3, 7, 15]]))