# Share my divide and conquer java solution, 464 ms

• 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;
}
}``````

• This post is deleted!

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

• 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!

• 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);
}
``````

};

• Nice solution!!!!!!

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