Recursively Merging Skylines


  • 0
    Y

    Although there exists an O(n2) solution, I will be describing the O(nlogn) solution here which uses recursion.

    The basic idea is to think in terms of skylines instead of buildings. So a single building of the form: [2,9,10] is actually a skyline of the form: [ [2,9] , [10,0] ]. Now we just need to think of a way to merge two skylines, which will allow us to recursively merge all our skylines together!

    CONVERT TO SKYLINES

    To begin, let's convert the buildings to skyline form so we don't have to juggle two data structures:

    skylines = []
        for b in buildings:   # b = [Li, Ri, Hi]
            skylines.append([[b[0], b[2]],[b[1], 0]])   # [ [Li,Hi] , [Ri,0] ]
    

    MERGE SKYLINES

    It's easier to introduce a new function, mergeSkylines(skylines) instead of dealing with the method we're given. This method takes a list of skylines, and returns a single skyline.

    def mergeSkylines(skylines):
         ...
         ...
         return skyline
    

    FIRST BASE CASE

    With usual recursion, we need a base case(s). In this case, we'll have two. The
    first is having 1 skyline in our list. If that happens, we just return it.

    if len(skylines) == 1:  # A single skyline is 'already merged'
        return skylines[0]    
    

    SECOND BASE CASE

    The second base case is when we have exactly two skylines. Merging them will require a bit of work. The code may seem intimidating, but there's a simple idea behind it. First we need to notice that a skyline will have an ascending x order:

    skyline = [[5, 12], [12, 0], [15, 10], [20, 8], [24, 0]]
    

    Let's say we want to merge these two skylines:

    skyline_l = [[2, 10], [9, 0]]
    skyline_r = [[3, 15], [7, 0]]
    

    We need to keep track of each skyline's height independently. The highest of either skyline will always be the resulting height. If the building is in the back, we'll see it. If it's in the front, we'll see. So max height always wins. That's the first trick.

    The second trick is to go through each point in skyline_l and skyline_r in order. And use that skyline's x value along with the highest y value from EITHER skyline.

    yl = 0
    yr = 0
    x = 0
    full_skyline = []
    
    while len(l_skyline) > 0 or len(r_skyline) > 0:
    
        xl = l_skyline[0]
        xr = r_skyline[0]
        
        if xl < xr:
            p = l_skyline.pop(0)
            x = p[0]
            yl = p[1]
            
        else:
            p = r_skyline.pop(0)
            x = p[0]
            yr = p[1]
            
        full_skyline.append([x,max(yl,yr)])
    

    Ops, what if one skylines ends?? We can catch that, and just add all the points from the non-empty skyline to our merged list. So the fixed code will look like:

    while len(l_skyline) > 0 or len(r_skyline) > 0:
                
        if len(l_skyline) == 0:
            full_skyline.extend(r_skyline)
            break
            
        if len(r_skyline) == 0:
            full_skyline.extend(l_skyline)
            break
            
        xl = l_skyline[0]
        xr = r_skyline[0]
        
        if xl < xr:
            p = l_skyline.pop(0)
            x = p[0]
            yl = p[1]
            
        else:
            p = r_skyline.pop(0)
            x = p[0]
            yr = p[1]
            
        full_skyline.append([x,max(yl,yr)])
    

    But wait, this might introduce successive points with the same height! We can fix that by going through our merged skyline and only keeping points that have a different height from the one before it:

    fixed_full_skyline = [full_skyline[0]]
    
    for p in full_skyline:
        if p[1] != fixed_full_skyline[-1][1]:
            fixed_full_skyline.append(p)
    

    MERGE STEP

    Ok that was a lot ... luckily the merge step is much simpler. Just merge the left and right halves of our skylines list. Then merge the resulting two skylines:

    skyline_1 = mergeSkylines( skylines[:num/2] )
    skyline_2 = mergeSkylines( skylines[num/2:] )
    return mergeSkylines([ skyline_1, skyline_2 ])
    

    Putting everything together, our solution will look like:

    def getSkyline(buildings):
        """
        :type buildings: List[List[int]]
        :rtype: List[List[int]]
        """
        
        # Convert single building into skyline
        skylines = []
        for b in buildings:
            skylines.append([[b[0], b[2]],[b[1], 0]])
        
        return mergeSkylines(skylines)   
    
    def mergeSkylines(skylines):
        
        num = len(skylines)
        
        if num == 1:
            return skylines[0]  
    
       	if num == 2:  
       		l_skyline = skylines[0]
    	    r_skyline = skylines[1]
    	    	        
    	yl = 0
    	yr = 0
    	x = 0
    	full_skyline = []
    
    	while len(l_skyline) > 0 or len(r_skyline) > 0:
    	            
    	    if len(l_skyline) == 0:
    	        full_skyline.extend(r_skyline)
    	        break
    	        
    	    if len(r_skyline) == 0:
    	        full_skyline.extend(l_skyline)
    	        break
    	        
    	    xl = l_skyline[0]
    	    xr = r_skyline[0]
    	    
    	    if xl < xr:
    	        p = l_skyline.pop(0)
    	        x = p[0]
    	        yl = p[1]
    	        
    	    else:
    	        p = r_skyline.pop(0)
    	        x = p[0]
    	        yr = p[1]
    	        
    	    full_skyline.append([x,max(yl,yr)])
    
    
    		fixed_full_skyline = [full_skyline[0]]
    
    		for p in full_skyline:
    		    if p[1] != fixed_full_skyline[-1][1]:
    		        fixed_full_skyline.append(p)
    	    
    	    return fixed_full_skyline
            
    	skyline_1 = mergeSkylines( skylines[:num/2] )
    	skyline_2 = mergeSkylines( skylines[num/2:] )
    	return mergeSkylines([ skyline_1, skyline_2 ])
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.