skyline

skyline.py

from heapq import heappop, heappush
class Solution:    
    
    def handle_end(self, h, res, item):
        end, height = item        
        while len(h) != 0 and h[0][1] <= end:
            heappop(h)
                
        if res[-1][1] == 0 or (len(h) != 0 and abs(h[0][0]) >= height):
            return
                    
        res.append((end, 0 if not len(h) else abs(h[0][0])))
    
    def handle_open(self, h, res, item):
        start, height, end = item
        if len(h) == 0 or height > abs(h[0][0]):
            if len(res) != 0 and res[-1][0] == start and res[-1][1] < height:
                res[-1] = (start, height)
            else:
                res.append((start, height))
        heappush(h, (0 - height, end))
    
    def split_intervals(self, buildings):        
        
        items = []
        
        for start, end, height in buildings:
            items.append((start, height, end))
            items.append((end, height))
        
        return items
    
    def getSkyline(self, buildings):
        """
        :type buildings: List[List[int]]
        :rtype: List[List[int]]
        """        
        
        h = []
        res = []                
        
        items = sorted(self.split_intervals(buildings), key=lambda element: (element[0], 0 - len(element)))
        
        for item in items:
            if len(item) == 3:
                self.handle_open(h, res, item)
            else:
                self.handle_end(h, res, item)
                
        return res