LC 218
TreeMap.
public List<int[]> getSkyline(int[][] buildings) {
List<int[]> res = new ArrayList<>();
if(buildings.length == 0) {
return res;
}
PriorityQueue<int[]> queue = new PriorityQueue<>((a, b) -> (a[0] == b[0]) ? b[1] - a[1]: a[0] - b[0]);
for(int[] building: buildings) {
queue.offer(new int[]{building[0], building[2]});
queue.offer(new int[]{building[1], -building[2]});
}
// TreeMap => RBT. So we can do both: get max/min value and insert/del elements in O(logN).
TreeMap<Integer, Integer> heightTree = new TreeMap<>(Collections.reverseOrder());
heightTree.put(0, 0);
while(!queue.isEmpty()) {
int[] point = queue.poll();
// New building occured.
if(point[1] > 0) {
// The new building is the heightest one.
if(point[1] > heightTree.firstKey()) {
res.add(new int[] {point[0], point[1]});
}
int count = heightTree.getOrDefault(point[1], 0);
heightTree.put(point[1], count + 1);
}
// A building reaches its end.
else {
int count = heightTree.get(-point[1]);
// The new building is the heightest one, and the only one.
if(count == 1) {
int firstKey = heightTree.firstKey();
heightTree.remove(-point[1]);
if(firstKey == -point[1]) {
res.add(new int[] {point[0], heightTree.firstKey()});
}
} else {
heightTree.put(-point[1], count - 1);
}
}
}
return res;
}