Java Solution Divide-and-Conquer Beat 95%


  • 1
    L

    The idea is from merge sort. We divide the buildings into two even parts, and divide-and-conquer skylines in each parts recursively. The tricky part would be how to merge the skylines from two parts. For simplicity, we suppose the two different parts only contain two skyline points (the basic situation) as:
    skyline1: (a, h1), (b, 0)
    skyline 2: (x, h2), (y, 0)

    We will discuss how to merge them in the following case:
    Case I y < b
    1.1 h2 <= h1: The output is {(a, h1), (b, 0)}
    0_1476758272051_upload-f1f40c70-5e0d-4cf0-a446-6b9cf140cd1a

    1.2 h2 > h1: The output is {(a, h1), (x, h2), (y, h1), (b, 0)}
    0_1476758414163_upload-4617da4d-381e-456f-8c76-f6a0c83adfa1

    Let’s focus on these two cases first to explain the merging procedure.
    Like merge sort, we assign two pointers p1 and p2 to the two skyline lists.
    Every time, we select the one with minimum x-axis value to proceed the merge, and increase the corresponding pointer. Let H1, H2 be two value that record the most recent height from skyline 1 and skyline 2 that has been processed, respectively.

    In case 1.1,
    step (1): we add (a, h1) to the result. After processing (a, h1), we assign H1 = h1.
    step (2): we process (x, h2), and we would add ( x, max(H1, h2) ) = (x, h1), but this duplicates previous value, hence is discarded. After this step, we assign H2 = h2.
    step (3): We process (y, 0), and we would add ( y, max(H1, 0) ) = (y, h1), but this duplicates previous value, hence is discarded. After this step, we assign H2 = 0.
    step (4): We process (b, 0), and we add ( b, max(0, H2) ) = (b, 0). After this step, we assign H1 = 0.

    In case 1.2,
    step (1): we add (a, h1) to the result. After processing (a, h1), we assign H1 = h1.
    step (2): we process (x, h2), and we add ( x, max(H1, h2) ) = (x, h2). After this step, we assign H2 = h2.
    step (3): We process (y, 0), and we add ( y, max(H1, 0) ) = (y, h1). After this step, we assign H2 = 0.
    step (4): We process (b, 0), and we add ( b, max(0, H2) ) = (b, 0). After this step, we assign H1 = 0.

    Similarly we can analyse the cases when y = b and y > b.

    The general rule is (In the following, given a skyline point s, we use s.x and s.height to represent the x-axis and the height, respectively.):
    (1) We compare the two leading elements s1 and s2 in skyline 1 and skyline 2 and select the one with smaller x-axis value as the current value (let it be cur).
    (2) if cur is from skyline 1, we set the merged point to be (cur.x, max{cur.height, H2} )
    (3) if cur is from skyline 2, we set the merged point to be (cur.x, max{cur.height, H1} )
    (4) if the merged point’s height is equal to the height of the last merged point, discard the current merge.

    The algorithm has O(n logn) complexity like merge sort, and the following implementation has beaten 95% java submissions.

    public class Solution {
        public List<int[]> getSkyline(int[][] buildings) {
            List<int[]> result = new ArrayList<int[]>();
            if(buildings == null || buildings.length == 0) return result;
            return computeSkyline(buildings, 0, buildings.length - 1);
        }
    
        public static int[] getPoint(int x, int y){
            int[] temp = {x, y};
            return temp;
        }
    
        private static List<int[]> computeSkyline(int[][] buildings, int from, int to){
            List<int[]> result = new ArrayList<int[]>();
            if(from == to){
                result.add(getPoint(buildings[from][0], buildings[from][2]));
                result.add(getPoint(buildings[from][1], 0));
                return result;
            }
            int mid = from + (to - from) / 2;
            List<int[]> LS1 = computeSkyline(buildings, from, mid);
            List<int[]> LS2 = computeSkyline(buildings, mid + 1, to);
            return merge(LS1, LS2);
        }
    
        public static List<int[]> merge(List<int[]> SL1, List<int[]> SL2){
            List<int[]> result = new ArrayList<int[]>();
            int len1 = SL1.size(), len2 = SL2.size();
            int p1 = 0, p2 = 0, H1 = 0, H2 = 0;
            int[] cur = null;
            // A boolean parameter to record whether the cur value is from
            // SL1 or SL2
            boolean fromSL1 = true;
            while(p1 < len1 && p2 < len2){
                int[] s1 = SL1.get(p1);
                int[] s2 = SL2.get(p2);
                if(s1[0] < s2[0]){
                    fromSL1 = true;
                    cur = s1;
                    H1 = cur[1];
                    ++p1;
                }
                else if(s1[0] > s2[0]){
                    fromSL1 = false;
                    cur = s2;
                    H2 = cur[1];
                    ++p2;
                }
                else{
                    if(s1[1] > s2[1]){
                        fromSL1 = true;
                        cur = s1;
                    }
                    else{
                        fromSL1 = false;
                        cur = s2;
                    }
                    H1 = s1[1];
                    H2 = s2[1];
                    ++p1; ++p2;
                }
                int h = 0;
                if(fromSL1) h = Math.max(cur[1], H2);
                else h = Math.max(cur[1], H1);
                if(result.isEmpty() || h != result.get(result.size() - 1)[1]){
                    result.add(getPoint(cur[0], h));
                }
            }
    
            while(p1 < len1) result.add(SL1.get(p1++));
            while(p2 < len2) result.add(SL2.get(p2++));
    
            return result;
        }
    }
    

  • 0
    S

    Awesome. Clear and fast.


  • 0
    L

    @SanFranciscoBuddy
    Thank you.


Log in to reply
 

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