Short Java solution


  • 167
    J
    	public List<int[]> getSkyline(int[][] buildings) {
        List<int[]> result = new ArrayList<>();
        List<int[]> height = new ArrayList<>();
        for(int[] b:buildings) {
            height.add(new int[]{b[0], -b[2]});
            height.add(new int[]{b[1], b[2]});
        }
        Collections.sort(height, (a, b) -> {
                if(a[0] != b[0]) 
                    return a[0] - b[0];
                return a[1] - b[1];
        });
        Queue<Integer> pq = new PriorityQueue<>((a, b) -> (b - a));
        pq.offer(0);
        int prev = 0;
        for(int[] h:height) {
            if(h[1] < 0) {
                pq.offer(-h[1]);
            } else {
                pq.remove(h[1]);
            }
            int cur = pq.peek();
            if(prev != cur) {
                result.add(new int[]{h[0], cur});
                prev = cur;
            }
        }
        return result;
    }

  • 0
    C

    This is an amazing answer and I don't understand why so little focus


  • 76
    M

    Thanks for the good solutions. However, there is a small thing that can be improved. pq.remove() is O(n) hence make it slower. I have modified it a little bit to use TreeMap instead of PriorityQueue and the run time is 2.5X faster.

    public class Solution {
        public List<int[]> getSkyline(int[][] buildings) {
            List<int[]> heights = new ArrayList<>();
            for (int[] b: buildings) {
                heights.add(new int[]{b[0], - b[2]});
                heights.add(new int[]{b[1], b[2]});
            }
            Collections.sort(heights, (a, b) -> (a[0] == b[0]) ? a[1] - b[1] : a[0] - b[0]);
            TreeMap<Integer, Integer> heightMap = new TreeMap<>(Collections.reverseOrder());
            heightMap.put(0,1);
            int prevHeight = 0;
            List<int[]> skyLine = new LinkedList<>();
            for (int[] h: heights) {
                if (h[1] < 0) {
                    Integer cnt = heightMap.get(-h[1]);
                    cnt = ( cnt == null ) ? 1 : cnt + 1;
                    heightMap.put(-h[1], cnt);
                } else {
                    Integer cnt = heightMap.get(h[1]);
                    if (cnt == 1) {
                        heightMap.remove(h[1]);
                    } else {
                        heightMap.put(h[1], cnt - 1);
                    }
                }
                int currHeight = heightMap.firstKey();
                if (prevHeight != currHeight) {
                    skyLine.add(new int[]{h[0], currHeight});
                    prevHeight = currHeight;
                }
            }
            return skyLine;
        }
    }

  • 0
    D

    this is acutally an excellent solution


  • 1
    C

    pq.remove() is log n.


  • 12
    M

    pq.poll() which remove the top of priority queue is O(log(n)), while pq.remove which remove any element is O(n) as it needs to search the particular element in all of the elements in the priority queue.


  • 0
    C

    awesome, thanks.


  • 0
    S

    what's the name of "->" please?. It's new to me and I didn't find how to use it because I don't even know what's it.....


  • 0
    E

    The underneath implementation of Priority Queue in java is Heap or RB-Tree?
    Why C++ STL priority_queue doesn't have remove() function?


  • 0
    G

    @shenhualonga: it used Java 8, which supports Lambda expression


  • 1
    W

    so sick, how did you come up with all this brilliant design...


  • 0
    A

    Why not use TreeSet? PQ is a set collection, but, TreeMap is a map collection.


  • 1
    M

    TreeSet can't handle duplicate height. Priority Queue allows two elements to be the same, but TreeSet doesn't allow that.


  • 0
    A

    Thank you for replying. You are right. TreeSet can't handle duplicates.


  • 0
    Y

    for those that don't have Java 8, here is another similar solution: https://leetcode.com/discuss/63521/java-solution-iteratively-checking-starting-ending-points
    It uses Comparator to sort the points


  • 0
    Y

    hi @jinwu, what is the intuition for this solution? esp. what is the intuition of <left, positive height> and <right, negative height>?


  • 0
    C

    Hi @jinwu, I am wondering why you are using a List to store the height instead of using another PriorityQueue?


  • 0
    C

    who can explain what's the idea behind this code?


  • 0
    F

    Good discussions above.


  • 2
    Y

    I got some explanation here, the mechanism is usually named sweepline. You can image a vertical line sweeping from left to right. https://leetcode.com/discuss/88149/java-solution-using-priority-queue-and-sweepline


Log in to reply
 

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