218. The Skyline Problem
这道题好麻烦，快要做吐了。首先写出一个TLE的版本，虽然是TLE吧，但是在面试里或许还是可以写一写的，毕竟一开始不要想去用很难的解法。如果yongheap的时候，要把解法1的loop内外层颠倒一下：
for each critical point c:
for each rectangle r above c (not including the right edge of rectangles):
c.y gets the max of r.height and the previous value of c.y
可以转化成：
for each critical point c
c.y gets the height of the tallest rectangle over c
这里利用heap来维护tallest rectangle就可以了，解法2的思路就是先把所有的点找出来排序，loop排好序的边界点，对于所有的building，如果building的左边界小于当前点，那么就push，push完毕后，如果building的右边界小于当前点，那么就pop
class Solution(object):
def getSkyline(self, buildings):
"""
:type buildings: List[List[int]]
:rtype: List[List[int]]
"""
if not buildings:
return []
# 首先拆分start end
arr = []
for b in buildings:
start, end, height = b
arr.append([start, height, "start"])
arr.append([end, 0, "end"])
arr = sorted(arr, key=lambda x:(x[0], x[2]))
# 对每个点更新它的高度值
for b in buildings:
for i in range(len(arr)):
if arr[i][0] >= b[0] and arr[i][0] < b[1]:
arr[i][1] = max(arr[i][1], b[2])
# loop所有关键点，生成答案
res = [[arr[0][0], arr[0][1]]]
for i in range(1, len(arr)):
if arr[i][1] == res[-1][1]:
continue
else:
res.append([arr[i][0], arr[i][1]])
return res
解法2
class Solution(object):
def getSkyline(self, buildings):
"""
:type buildings: List[List[int]]
:rtype: List[List[int]]
"""
def addsky(pos, hei):
if sky[-1][1] != hei:
sky.append([pos, hei])
sky = [[-1,0]]
# possible corner positions
position = set([b[0] for b in buildings] + [b[1] for b in buildings])
# live buildings
live = []
i = 0
for t in sorted(position):
# add the new buildings whose left side is lefter than position t
# 先把较小的building都加进去
while i < len(buildings) and buildings[i][0] <= t:
heapq.heappush(live, (-buildings[i][2], buildings[i][1]))
i += 1
# remove the past buildings whose right side is lefter than position t
# 再把不符合的building都pop出来
while live and live[0][1] <= t:
heapq.heappop(live)
# pick the highest existing building at this moment
h = -live[0][0] if live else 0
addsky(t, h)
return sky[1:]
