# Lazy Segment Tree Solution (22ms)

• ``````public class Solution {
static class TreeNode{
TreeNode left, right;
int h;
boolean isGap;
TreeNode(int h){
this.h = h;
this.left = null;
this.right = null;
this.isGap = false;
}
}
public List<int[]> getSkyline(int[][] buildings) {
List<int[]> res = new ArrayList<>();
if(null == buildings) return res;
int n = buildings.length;
if(n==0) return res;
TreeNode root = new TreeNode(-1);
int  maxEnd = -1;
for(int [] building : buildings){
if(maxEnd != -1 && building[0] > maxEnd){
update(root, 0, Integer.MAX_VALUE, maxEnd, maxEnd, 0);// isGap
}
update(root, 0, Integer.MAX_VALUE, building[0], building[1], building[2]);
// System.out.println("-----------");
maxEnd = Math.max(maxEnd, building[1]);
}

query(root, 0, Integer.MAX_VALUE, res);
// Collections.sort(res, new Comparator<int[]>(){
//     @Override
//     public int compare(int [] arr1, int [] arr2){
//         return arr1[0]-arr2[0];
//     }
// });
return res;
}
void update(TreeNode root, int l, int r, int ql, int qr, int h){
if(l == ql && r == qr && root.left == null && root.right == null){// lazy
root.h = Math.max(root.h, h);
if(h == 0) root.isGap = true;
// System.out.println(l + "\t" +r + "\t" + root.h);
return;
}

int mid = l + (r-l) /2;

if(root.h >= 0){
if(root.left == null) root.left = new TreeNode(-1);
update(root.left, l, mid, l, mid, root.h);
if(root.right == null) root.right = new TreeNode(-1);
update(root.right, mid+1, r, mid+1, r, root.h);
root.h = -1;
}

if(mid >= qr) {
if(root.left == null) root.left = new TreeNode(-1);
update(root.left, l, mid, ql, qr, h);
}
else if(mid < ql){
if(root.right == null) root.right = new TreeNode(-1);
update(root.right, mid+1, r, ql, qr, h);
}
else{
if(root.left == null) root.left = new TreeNode(-1);
if(root.right == null) root.right = new TreeNode(-1);
update(root.left, l, mid, ql, mid, h);
update(root.right, mid+1, r, mid+1, qr, h);
}
}

void query(TreeNode root, int l, int r, List<int[]> res){
if(root == null) return;
if(root.h >= 0){
// System.out.println(l + "\t" + r + "\t" + root.h);
if(res.isEmpty() || res.get(res.size()-1)[1] != root.h){
if(!res.isEmpty() && res.get(res.size()-1)[1] > root.h) res.add(new int[] {l-1, root.h});
}
if(root.isGap){