218. The Skyline Problem

line sweep

model each building as 2 events
- top left point is modeled as a start event with height of the height of the building
- top right is modeled as an end event with height of 0
sort events by position
- edge case 1: duplicated end events can be removed by using set
- edge case 2: for multiple events starting from same position, the higher one should take precedence.
  - In other words, events should be sorted by position in ascending order then sorted by height in descending order.
  - This also explains why event[0] is start position and event[1] is negative height
using a heap to track the max height among active events. If a new event added to heap cause change of skyline, it should be added to result list as a key point of the skyline
- how to detect change of skyline: compare current max height proved by heap and previous max height provided by result list
- how to maintain active events:
  - compare start position of new event and end position of the even on top of heap.
    - This explains why we need event[2] to store end position of each start event
    - It also explains why we need end event: to kick out inactive start events
  - There may still be inactive events in heap, but they have no impact to skyline since their heights are low

class Solution:
    def getSkyline(self, buildings):
        '''
        event structure where 
            event[0] is starting position of the event
            event[1] is negative height of the event
            event[2] is ending position of the event
        '''
        startEvents = [(left, -height, right) for left, right, height in buildings]
        '''
        An end event is interpreted as an event of height 0 which starts 
        from right, and ends at an infinite position
        
        using set to get rid of duplicated end events
        '''
        endEvents = list({(right, 0, None) for _, right, _ in buildings})
        
        '''
        1. events are sorted by starting position in ascending order
        2. events with same starting position are sorted in descending 
            order by height: we will need to push those event into max heap
            Pushing higher event then lower one so that higher one can hide 
            lower one. Otherwise we will record lower one as a key point as well as higher one
        '''
        events = sorted(startEvents + endEvents)
        
        '''
        res is used to record result.
        It is also used to record previous max heigh while scanning all                 events. 
        Initially put a dummy record [0, 0] into it
        '''
        res = [0, 0](/cocoder39/coco39_LC/wiki/0,-0)
        
        '''
        maxHeap maintains a max heap for elements where 
            maxHeap[i][0] is the negative height and 
            maxHeap[i][1] is the ending position of the height
        
        Initially put a dummy record [0, infinite] into it
        '''
        maxHeap = [(0, float("inf"))]
        for start, negH, end in events:
            # kick out inactive events
            # there may still be inactive events in maxHeap but they don't impact correctness since they don't have the max height. Ideally they should be removed for better performance but python is ineffective in removing an item by key (T = O(n)). The lazy removal is a comprise of corectness and performance
            while start >= maxHeap[0][1]: 
                heapq.heappop(maxHeap)
            
            # add starting event into heap
            if negH < 0: 
                heapq.heappush(maxHeap, (negH, end))
            
            # current max height is different from previous max height
            if res[-1][1] != -maxHeap[0][0]: 
                res.append([start, -maxHeap[0][0]])
        return res[1:]

218. The Skyline Problem - cocoder39/coco39_LC GitHub Wiki