the skyline problem

🏠
 1 from heapq import heappush, heappop
 2 from collections import namedtuple
 3 
 4 Point = namedtuple("Point", "y x1")
 5 ResPoint = namedtuple("ResPoint", "x y")
 6 
 7 
 8 class 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 
26 print(Solution().getSkyline([[2, 9, 10], [3, 7, 15]]))