# 24 ms solution using segment tree

• ``````public class Solution {
class TreeNode {
int left;
int right;
int height;
TreeNode leftChild = null;
TreeNode rightChild = null;
public TreeNode(int l, int r, int h) {
left = l;
right = r;
height = h;
}
}
public List<int[]> getSkyline(int[][] buildings) {
List<int[]> result = new ArrayList<>();
if (buildings == null || buildings.length == 0 || buildings[0].length == 0) return result;
int[] leftAndRightEnd = findLeftAndRightEnd(buildings);
int leftEnd = leftAndRightEnd[0];
int rightEnd = leftAndRightEnd[1];
TreeNode root = new TreeNode(leftEnd, rightEnd, 0);
for (int[] building : buildings) {
insertInTree(root, building[0], building[1] - 1, building[2]);
}
traverseAndFindKeyPoints(root, result);
return collapse(result);
}

List<int[]> collapse(List<int[]> keyPoints) {
List<int[]> result = new ArrayList<>();
int[] lastKeyPoint = keyPoints.get(0);
for (int i = 1; i < keyPoints.size(); i++) {
int[] keyPoint = keyPoints.get(i);
if (keyPoint[1] != lastKeyPoint[1]) {
lastKeyPoint = keyPoint;
}
}
return result;
}

int[] findLeftAndRightEnd(int[][] buildings) {
int[] result = new int[] {Integer.MAX_VALUE, Integer.MIN_VALUE};
for (int[] building : buildings) {
result[0] = Math.min(result[0], building[0]);
result[1] = Math.max(result[1], building[1]);
}
return result;
}

void insertInTree(TreeNode root, int left, int right, int height) {
if (root == null) return;
if (left > root.right || right < root.left) return;
int mid = root.left / 2 + root.right / 2;
if (root.left >= left && root.right <= right) {
root.height = Math.max(root.height, height);
if (root.leftChild == null && root.rightChild == null) return;
}

makeChildrenIfApplicable(root, mid);

if (left < mid + 1) {
insertInTree(root.leftChild, left, right, height);
}
if (right > mid) {
insertInTree(root.rightChild, left, right, height);
}
}

void makeChildrenIfApplicable(TreeNode root, int mid) {
if (mid == root.right) return;
if (root.leftChild == null) root.leftChild = new TreeNode(root.left, mid, root.height);
if (root.rightChild == null) root.rightChild = new TreeNode(mid + 1, root.right, root.height);
}

void traverseAndFindKeyPoints(TreeNode root, List<int[]> result) {
if (root == null) return;

traverseAndFindKeyPoints(root.leftChild, result);
if (root.leftChild == null && root.rightChild == null) {