LeetcodeTheSkylineProblem.java

publicclassSolution {
publicList<int[]> getSkyline(int[][] buildings) {
returnmerge(buildings, 0, buildings.length-1);
 }

privateLinkedList<int[]> merge(int[][] buildings, intlo, inthi) {
LinkedList<int[]> res = newLinkedList<>();
if(lo > hi) {
returnres;
 } elseif(lo == hi) {
res.add(newint[]{buildings[lo][0], buildings[lo][2]});
res.add(newint[]{buildings[lo][1], 0});
returnres;
 } 
intmid = lo+(hi-lo)/2;
LinkedList<int[]> left = merge(buildings, lo, mid);
LinkedList<int[]> right = merge(buildings, mid+1, hi);
intleftH = 0, rightH = 0;
while(!left.isEmpty() || !right.isEmpty()) {
longx1 = left.isEmpty()? Long.MAX_VALUE: left.peekFirst()[0];
longx2 = right.isEmpty()? Long.MAX_VALUE: right.peekFirst()[0];
intx = 0;
if(x1 < x2) {
int[] temp = left.pollFirst();
x = temp[0];
leftH = temp[1];
 } elseif(x1 > x2) {
int[] temp = right.pollFirst();
x = temp[0];
rightH = temp[1];
 } else {
x = left.peekFirst()[0];
leftH = left.pollFirst()[1];
rightH = right.pollFirst()[1];
 }
inth = Math.max(leftH, rightH);
if(res.isEmpty() || h != res.peekLast()[1]) {
res.add(newint[]{x, h});
 }
 }
returnres;
 }
}