[LeetCode] 218. The Skyline Problem

Problem : https://leetcode.com/problems/the-skyline-problem/

Use divide-and-conquer approach. 

Merging process:

- Pick the item with smaller X in left or right group.

- Update left-height or right-height.

- current-height = max( left-height, right-height )

- Update skyline if current-height is changed

Time Complexity = O ( N * Log N )

from operator import itemgetter
class Solution:
    def getSkyline(self, buildings: List[List[int]]) -> List[List[int]]:
        def update(result, x, h):
            if not result or result[-1][0] != x:
                # add new key point
                result.append([x, h])
            else:
                # update the last key point height
                result[-1][1] = h
                
        def append(result, lst, p, n, h, ch):
            while p < n:
                x, h = lst[p]
                p += 1
                
                if ch != h:
                    update(result, x, h)
                    ch = h
        
        def merge(left, right):
            nl, nr = len(left), len(right)
            pl = pr = 0
            
            # current hight, left hight, right hight
            ch = lh = rh = 0
            
            result = []
            
            while pl < nl and pr < nr:
                lpx, lph = left[pl]
                rpx, rph = right[pr]
                
                x = 0
                if lpx < rpx:
                    x, lh = lpx, lph
                    pl += 1
                else:
                    x, rh = rpx, rph
                    pr +=1 
                
                # use the maximum height 
                max_h = max(lh, rh)
                
                # update / add point if maximum height changes
                if ch != max_h:
                    update(result, x, max_h)
                    ch = max_h
       
            append(result, left, pl, nl, lh, ch)
            append(result, right, pr, nr, rh, ch)

            return result
                    
                    
        def divideAndConqure(start, end):
            if end == start:
                # skyline for zero building
                return []
            
            if end - start == 1:
                # skyline for one building
                l, r, h = buildings[start]
                return [[l, h], [r, 0]]
            
            # divide buildings into two groups and calculate skyline respectively
            mid = start + (end - start) // 2
            left_skyline = divideAndConqure(start, mid)
            right_skyline = divideAndConqure(mid, end)
            
            # merge left and right skyline
            return merge(left_skyline, right_skyline)
        
        return divideAndConqure(0, len(buildings))