The skyline Problem

'''
Observation:Change is only possible at building start or end.
so break the starting and ending point of building where height at starting point will be positive of height
and at ending point negative height so that we can differentiate between starting and ending point.
eg (2,9,13) -> (2,13) and (9,-13)
sort the above list because answer asked in question is in sorted order.

Let's say building present at current point is active buildings so,outline is maximum height among active buildings.
so we maintain a max_heap which will maintain the maximum height building at top and that building is active or not,
that can be taken care by map.
so whenever we see positive height,means start of building then
    if it's abs(height)>cur_height push it into answer,active building and map and also update the current_height.
    if it's abs(height)<=cur_height push it into active building and map
if current height is negative means end of building:
    if it's height is same as cur_height,then remove that height from map,and find the maximum height among the
    active buildings and update the cur_height if cur_height is different and update the answer else keep it same
    Test Case: [[0,2,3],[2,5,3]]

    else remove from map.

One more example is : [0,2],[2,-2],[2,2],[4,-2] ans : [0,2],[4,0]
here first building is ending at point 2 and second building is starting again at 2 so while sorting we will add first so my_fun is created otherwise answer in our above example will be at 2 is [2,0] then again go to [2,2].
'''

from heapq import heappush, heappop
from typing import List

class Solution:
    def getSkyline(self, buildings: List[List[int]]) -> List[List[int]]:
        arr = []
        heap = []
        dict = {}
        ans = []
        cur_max = 0
        for l, r, h in buildings:
            arr.append([l, h])
            arr.append([r, -h])

        arr.sort(key=lambda x: (x[0], -x[1])) #this is needed because if at x cordinate i, if one building finises and other building starts at same point,then if you won't bring the starting building first in the array,it will put a break in the skyline in the answer array.
        for x, h in arr:
            if h > 0:
                heappush(heap, -h)
                dict[h] = dict.get(h, 0) + 1

                if h > cur_max:
                    cur_max = h
                    ans.append([x, cur_max])
            else:
                height = -h
                dict[height] -= 1
                while heap and dict.get(-heap[0], 0) == 0:
                    heappop(heap)

                new_max = -heap[0] if heap else 0 #if there is no building,then ground would be the skyline.
                if new_max != cur_max: #!=cur_max is needed because there are chances of same height building there.
                    cur_max = new_max
                    ans.append([x, cur_max])

        return ans