My java solution using a MAX queue.


  • 0
    Q
    public class Solution {
        public static class Data implements Comparable<Data>{
            int val;  // x value
            int height;
            boolean flag; // indicate a start line or a end line
            public Data(int v,int h,boolean f){
                this.val = v;
                this.height = h;
                this.flag = f;
            }
            boolean isStart(){
                return flag;
            }
            // sort the Data according to x val, start or end, height
            public int compareTo(Data other){
                if(val != other.val){
                    return val - other.val;
                }else if(flag != other.flag){
                    return flag?1:-1;
                }else if(height != other.height){
                    if(flag) return other.height - height;
                    else return height - other.height;
                }
                return 0;
            }
        }
        public static List<int[]> getSkyline(int[][] buildings) {
            List<int[]> res = new ArrayList<int[]>();
            ArrayList<Data> building = new ArrayList<Data>();
            for(int i=0;i<buildings.length;i++){
                building.add(new Data(buildings[i][0],buildings[i][2],true));
                building.add(new Data(buildings[i][1],buildings[i][2],false));
            }
            Collections.sort(building);
            // store the height;
            PriorityQueue pq = new PriorityQueue<Integer>(10,Collections.reverseOrder());
            Data prev = null;
            for(int i=0;i<building.size();i++){
                Data d = building.get(i);
                Data next = i+1<building.size()?building.get(i+1):null;
                if(d.isStart()){
                    // is the current start line is the same with the previous one, ignore it
                    if(prev== null || !(d.height == prev.height && d.val == prev.val)){
                        if(pq.isEmpty()){
                            res.add(new int[] {d.val,d.height});
                        }else if(d.height >(int) pq.peek()){
                            res.add(new int[]{d.val,d.height});
                        }
                    }
                    // whenever it is a start line, add it to the PQ
                   pq.add(d.height);
                }else if(!d.isStart()){
                        // whenever it is a end line, remove it from the PQ
                       pq.remove(d.height);
                       // if the current end line has the same x value with the next line, ignore it
                       if(next == null || d.val != next.val){
                           if(!pq.isEmpty() && d.height > (int)pq.peek()){
                                res.add(new int[]{d.val,(int)pq.peek()});
                           }else if(pq.isEmpty()){
                                res.add(new int[]{d.val,0});
                            }
                       }
                }
                prev= d;
            }
            return  res;
        }
    }

Log in to reply
 

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