218. The Skyline Problem.md

218. The Skyline Problem (Hard)

• add (rise time, height) and (end time, -height) to one list.
• sorted by time min->x, when time are the same, sorted by height max - min. Because if a building is rise when a building is end, we need to increase the sky line then remove the lower sky line.
• if the height is positive, add it to the max heap. if negitive, delete it from the heap.
• add record the ans of (time, height) when the height is changed. use a prevHeight and curHeight for logging the height change.
• heapq does not have remove function so needs to use SortedList

from sortedcontainers import SortedList
class Solution:
    def getSkyline(self, buildings: List[List[int]]) -> List[List[int]]:
        timeList = []
        ans = []
        heightSorted = SortedList(key = lambda x:-x)
        for oneBuilding in buildings:
            timeList.append([oneBuilding[0], oneBuilding[2]])
            timeList.append([oneBuilding[1], -oneBuilding[2]])
        timeList.sort(key = lambda x: (x[0], -x[1]))
        heightSorted.add(0)
        preHeight = 0
        for oneTime in timeList:
            if oneTime[1] > 0:
                # push negitive value for max heap
                heightSorted.add(oneTime[1])
            else:
                heightSorted.remove(-oneTime[1])
            curHeight = heightSorted[0]
            if curHeight != preHeight:
                ans.append([oneTime[0], curHeight])
                preHeight = curHeight
        return ans