Clean Java solution using two PriorityQueues


  • 2
    J

    Here is working Java solution that uses two PriorityQueues:

    • the first one - min oriented that stores the building end (x2) coordinates
    • the second one - max oriented that stores the heights of the buildings

    The main loop iterates over each of the building and adds it to the queues in the same time it tries to remove all the buildings that x2 coordinate is less then current building x1 coordinate.

    There are some edge cases to consider, for instance what in case that there are multiple buildings with exactly same x1 and x2 coordinates i.e. [1, 1, 2], [1, 1, 1] ...

    Enjoy


    public class Solution {
        public List<int[]> getSkyline(int[][] buildings) {
            if(buildings == null || buildings.length == 0) {
                return Collections.emptyList();
            }
    
            final PriorityQueue<Building> endings = new PriorityQueue<>((v1, v2) -> Integer.compare(v1.to, v2.to));
            final PriorityQueue<Integer> heights = new PriorityQueue<>((v1, v2) -> Integer.compare(v2, v1));
    
            final List<int[]> result = new ArrayList<>();
    
            // iterate over each of the building
            for(int[] build : buildings) {
                final Building building = new Building(build);
    
                while (endings.size() > 0 && endings.peek().to < building.from) {
                    removeBuildings(endings, heights, result);
                }
    
                if(heights.size() == 0 || building.height > heights.peek()) {
                    result.add(new int[]{building.from, building.height});
                }
                heights.add(building.height);
                endings.add(building);
            }
    
            while(endings.size() > 0) {
                removeBuildings(endings, heights, result);
            }
    
            return result;
        }
        
         private void removeBuildings(PriorityQueue<Building> endings, PriorityQueue<Integer> heights, List<int[]> result) {
            final Building rm = endings.poll();
            heights.remove(rm.height);
            while(endings.size() > 0 && endings.peek().to == rm.to) {
                heights.remove(endings.poll().height);
            }
            final int peek = heights.size() > 0 ? heights.peek() : 0;
            if(peek < rm.height) {
                result.add(new int[]{rm.to, peek});
            }
        }
    
        private static class Building {
            private final int from;
            private final int to;
            private final int height;
            
            public Building(int[] building) {
                this.from = building[0];
                this.to = building[1];
                this.height = building[2];
            }
        }
    }

  • 0
    G

    you implemented Lambda function :) nice


  • 0
    T

    how does:
    final PriorityQueue<Building> endings = new PriorityQueue<>((v1, v2) -> Integer.compare(v1.to, v2.to));
    specifically:
    ((v1, v2) -> Integer.compare(v1.to, v2.to));
    work?


  • 0
    J

    Those are Java 8 lambdas. In fact if the prority queue would store primivite type (in fact the wrapper types like Integer or Long) it would be more convienient to use Collections.reverseOrder() method for the heights PriorityQueues.

    You can find the basic introduction to lambda expressions in Java here: https://docs.oracle.com/javase/tutorial/java/javaOO/lambdaexpressions.html


  • 0
    L

    your code is not accepted. Submission Result: Wrong Answer


Log in to reply
 

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