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


  • 0
    S

    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;
        }
    }
    

    }


Log in to reply
 

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