# TreeMap solution, guaranteed to O(n logN)

• I scan all the points, while keeping a map of all existing heights:

``````class heightComparator implements Comparator<int[]> {

@Override
public int compare(int[] o1, int[] o2) {
// if both arrays are at the same position, put the one with greater height first
if (o1[0] != o2[0])
return o1[0] - o2[0];
else
return o2[1] - o1[1];
}

}
public class Solution {
public List<int[]> getSkyline(int[][] buildings) {
List<int[]> res = new ArrayList<>();
if (buildings == null || buildings.length == 0)
return res;
int n = buildings.length;
int[][] heights = new int[2 * n][2];
for (int i =  0; i < n; ++i) {
//e.g. for  [ [2 9 10], [3 7 15], [5 12 12], [15 20 10], [19 24 8] ], store [2  10], [9, -10]
heights[2 * i][0] = buildings[i][0];
heights[2 * i][1] = buildings[i][2];

heights[2 * i + 1][0] = buildings[i][1];
heights[2 * i + 1][1] = -buildings[i][2];
}

Arrays.sort(heights, new heightComparator());

// Then scan from left to right
TreeMap<Integer, Integer> cnt = new TreeMap<>();

for (int i = 0; i < 2 * n; ++i) {
int this_pos = heights[i][0];
int this_height = heights[i][1];
if (this_height > 0) {
cnt.put(this_height, cnt.getOrDefault(this_height, 0) + 1);
} else {
int this_cnt = cnt.get(-this_height);
if (this_cnt > 1) {
cnt.put(-this_height, this_cnt - 1);
} else
cnt.remove(-this_height);
}

if (i < 2 * n - 1 && heights[i][0] == heights[i + 1][0])
continue;

// try to update with new height
int cur_height = (cnt.isEmpty()) ? 0 : cnt.lastKey();
if (res.size() == 0 || cur_height != res.get(res.size() - 1)[1])