beat 90% Java


  • 0
    Y

    class Solution {
    class Side{
    int pos;
    int height;
    boolean inOrOut;
    Side inSide;

        public Side(int p, int h, boolean i){
            pos = p;
            height = h;
            inOrOut = i;
        }
        
    }
    
    class TimeCompare implements Comparator<Side>{
        @Override
        public int compare(Side s1, Side s2){
            return s1.pos - s2.pos;
        }
    }
    
    class HeightCompare implements Comparator<Side>{
        @Override
        public int compare(Side s1, Side s2){
            return s2.height - s1.height;
        }
    }
    
    
    public List<int[]> getSkyline(int[][] buildings) {
        List<int[]> res = new LinkedList<int[]>();
        
        if(buildings.length != 0){
            List<Side> sides = new ArrayList<Side>();
            for(int[] building: buildings){
                Side inSide = new Side(building[0], building[2], true);
                Side outSide = new Side(building[1], building[2], false);
                outSide.inSide = inSide;
                sides.add(inSide);
                sides.add(outSide);
            }
            Collections.sort(sides, new TimeCompare());
            
            PriorityQueue<Side> pq = new PriorityQueue<Side>(buildings.length*2, new HeightCompare());
            
            int height = 0;
            
            for(int i = 0; i < sides.size(); i++){
                Side side = sides.get(i);
                if(side.inOrOut){
                    pq.offer(side);
                }else{
                    pq.remove(side.inSide);
                }
                if(i == sides.size()-1 || sides.get(i+1).pos != side.pos){
                    if(pq.peek() == null){
                        res.add(new int[]{side.pos, 0});
                    }else{
                        if(pq.peek().height != height){
                            height = pq.peek().height;
                            res.add(new int[]{side.pos, height});
                        }
                    }
                }
            }
        }
        
        return res;
    }
    

    }


Log in to reply
 

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