My Java AC code with PriorityQueues


  • 2
    N

    The idea is to sort all critical points first. Then keep track of an active set of buildings with a max priority queue. When it comes to the left edge of a building, add its height to the maxPQ. When it comes to the right edge, remove the height. The add/remove operation for pq takes logN time, peek operation is constant time. The overall time complexity should be O(n * log(n)).

    class Pair implements Comparable<Pair> {
        int index;
        int height;
        Pair(int i, int h) {
            this.index = i;
            this.height = h;
        }
    
        public int compareTo(Pair p) {
            // if index is different, smaller index comes first
            if (this.index != p.index) return this.index - p.index;
            // if the right end and left start overlap, left start point comes first
            if (p.height * this.height < 0) return this.height - p.height;
            // overlap on the left edge, the bigger value comes first
            if (this.height < 0 && p.height < 0) return Math.abs(p.height) - Math.abs(this.height);
            // overlap on the right value, the smaller values comes first
            return Math.abs(this.height) - Math.abs(p.height);
        }
    
    }
    
    public class Solution {
        public List<int[]> getSkyline(int[][] buildings) {
            List<int[]> result = new LinkedList();
            if (buildings == null || buildings.length == 0) return result;
            int len = buildings.length;
            Pair[] pairs = new Pair[2 * len];
            for (int i = 0; i < len; i++) {
                pairs[2 * i] = new Pair(buildings[i][0], -buildings[i][2]);
                pairs[2 * i + 1] = new Pair(buildings[i][1], buildings[i][2]);
            }
            Arrays.sort(pairs);
            int height = 0;
            // Priority queue in java allows duplicates
            PriorityQueue<Integer> maxPQ = new PriorityQueue<Integer>(len, Collections.reverseOrder());
            for (Pair p: pairs) {
                if (p.height < 0) maxPQ.add(-p.height);
                else maxPQ.remove(p.height);
                int newH = (maxPQ.peek() == null) ? 0 : maxPQ.peek();
                if (newH != height) {
                    height = newH;
                    int[] re = new int[2];
                    re[0] = p.index;
                    re[1] = height;
                    result.add(re);
                }
            }
            return result;
        }
    }

  • 2
    K

    nice solution.
    One minor improvement:

    if (p.height * this.height < 0) return this.height - p.height;
    // overlap on the left edge, the bigger value comes first
    if (this.height < 0 && p.height < 0) return Math.abs(p.height) - Math.abs(this.height);
    // overlap on the right value, the smaller values comes first
    return Math.abs(this.height) - Math.abs(p.height);
    

    could be replace by just:

    return this.height - p.height;

  • 0
    A

    removing from a heap is o(logn)? I am not sure about that..


  • 0
    L

    amitdutta, it's O(n) in java's PriorityQueue, cuz it need to find the element first although the reshuffle of max heap takes O(lgn)


  • 0
    C

    I think actually n + log(n), n for find, and log(n) from restore heap. But if you can keep some auxiliary data structure to eliminate n, then it can be log(n)


  • 0
    L

    O(n+lgn) is just O(n).


Log in to reply
 

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