Share my divide and conquer java solution, 464 ms


  • 68
    H

    Detailed explanation: http://www.geeksforgeeks.org/divide-and-conquer-set-7-the-skyline-problem/

    public class Solution {
    	public List<int[]> getSkyline(int[][] buildings) {
    		if (buildings.length == 0)
    			return new LinkedList<int[]>();
    		return recurSkyline(buildings, 0, buildings.length - 1);
    	}
    
    	private LinkedList<int[]> recurSkyline(int[][] buildings, int p, int q) {
    		if (p < q) {
    			int mid = p + (q - p) / 2;
    			return merge(recurSkyline(buildings, p, mid),
    					recurSkyline(buildings, mid + 1, q));
    		} else {
    			LinkedList<int[]> rs = new LinkedList<int[]>();
    			rs.add(new int[] { buildings[p][0], buildings[p][2] });
    			rs.add(new int[] { buildings[p][1], 0 });
    			return rs;
    		}
    	}
    
    	private LinkedList<int[]> merge(LinkedList<int[]> l1, LinkedList<int[]> l2) {
    		LinkedList<int[]> rs = new LinkedList<int[]>();
    		int h1 = 0, h2 = 0;
    		while (l1.size() > 0 && l2.size() > 0) {
    			int x = 0, h = 0;
    			if (l1.getFirst()[0] < l2.getFirst()[0]) {
    				x = l1.getFirst()[0];
    				h1 = l1.getFirst()[1];
    				h = Math.max(h1, h2);
    				l1.removeFirst();
    			} else if (l1.getFirst()[0] > l2.getFirst()[0]) {
    				x = l2.getFirst()[0];
    				h2 = l2.getFirst()[1];
    				h = Math.max(h1, h2);
    				l2.removeFirst();
    			} else {
    				x = l1.getFirst()[0];
    				h1 = l1.getFirst()[1];
    				h2 = l2.getFirst()[1];
    				h = Math.max(h1, h2);
    				l1.removeFirst();
    				l2.removeFirst();
    			}
    			if (rs.size() == 0 || h != rs.getLast()[1]) {
    				rs.add(new int[] { x, h });
    			}
    		}
    		rs.addAll(l1);
    		rs.addAll(l2);
    		return rs;
    	}
    }

  • 0
    H
    This post is deleted!

  • 0
    T

    Thanks for the divide and conquer idea, this is very easy to understand.


  • 0

    The C++ solution in geeksforgeeks has a flaw, when two strips happen to have the same position, and the merged height of the new strip is wrong. Thanks for fixing that bug!


  • 5
    P

    Good solution. Here is the C++ solution using the same logic :

    class Solution {
    

    public:

    vector< pair<int,int> > merge(vector< pair<int,int> > &A,vector< pair<int,int> > &B)
    {
         vector<pair<int,int>> C;
         int h1 = 0,h2 = 0,i = 0,j = 0;
         while(i < A.size() && j < B.size())
         {
             int x = 0,h = 0;
             if(A[i].first < B[j].first)
             {
                 x = A[i].first;
                 h1 = A[i].second;
                 h = max(h1,h2);
                 i++;
             }
             else if(A[i].first > B[j].first)
             {
                 x = B[j].first;
                 h2 = B[j].second;
                 h = max(h1,h2);
                 j++;
             }
             else
             {
                 x = A[i].first;
                 h1 = A[i].second;
                 h2 = B[j].second;
                 h = max(h1,h2);
                 i++,j++;
             }
             if(C.size() == 0 || h != C[C.size()-1].second)
                C.push_back(make_pair(x,h));
         }
         while(i < A.size())
            C.push_back(A[i++]);
         while(j < B.size())
            C.push_back(B[j++]);
        return C;
    }
        
    vector< pair<int,int> > recurSkyline(vector< vector<int> > &A,int start,int end)
    {
        if(end > start)
        {
            int mid = start + (end-start)/2;
            vector< pair<int,int> > B = recurSkyline(A,start,mid);
            vector< pair<int,int> > C = recurSkyline(A,mid+1,end);
            return merge(B,C);
        }
        else
        {
            vector<pair<int,int>> V;
            V.push_back(make_pair(A[start][0],A[start][2]));
            V.push_back(make_pair(A[start][1],0));
            return V;
        }
    }
    
    vector<pair<int, int>> getSkyline(vector<vector<int>>& A)
    {
        vector<pair<int,int>> V;
        if(A.size() == 0)
            return V;
        return recurSkyline(A,0,A.size()-1);
    }
    

    };


  • 0
    B

    Nice solution!!!!!!


Log in to reply
 

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