# 31ms beats 86.85% Java Solution using PriorityQueue O(nlogn) time and O(n) space

• public class Solution {

``````public List<int[]> getSkyline(int[][] buildings) {

List<int[]> results = new ArrayList<int[]>();
if (buildings == null || buildings.length == 0 || buildings[0] == null || buildings[0].length == 0){
return results;
}

ArrayList<Node> input = new ArrayList<Node>();
for (int i = 0; i < buildings.length; i++){
Node begin = new Node(buildings[i][0], buildings[i][2]);
input.add(begin);
Node end = new Node(buildings[i][1], buildings[i][2]);
end.begin = begin;
input.add(end);
}

Collections.sort(input, new Comparator<Node>(){
@Override
public int compare(Node node1, Node node2){
return node1.x - node2.x;
}
});

PriorityQueue<Node> priorityQ = new PriorityQueue<Node>(buildings.length, new Comparator<Node>(){
@Override
public int compare(Node node1, Node node2){
return node2.y - node1.y;
}
});  //maxHeap

int curr = -1;
for (Node node : input){
int val = 0;
if (node.begin == null){ //left edge
priorityQ.offer(node);
val = priorityQ.peek().y;
} else {           //right edge
priorityQ.remove(node.begin);
val = priorityQ.isEmpty() ? 0 : priorityQ.peek().y;
}
if (curr != val){
if (results.size() - 1 >= 0 && node.x == results.get(results.size() - 1)[0]){
int[] prev = results.get(results.size() - 1);
prev[1] = val;
curr = prev[1];
if (results.size() - 2 >= 0 && results.get(results.size() - 2)[1] == prev[1]){
results.remove(results.size() - 1);
}
} else {
int[] res = {node.x, val};
results.add(res);
curr = val;
}
}
}
return results;
}

class Node{
int x;
int y;
Node begin;  //for the left edge, begin is null. For the right edge, it points to its left edge.
Node(int x, int y){
this.x = x;
this.y = y;
}
}
``````

}

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.