257ms Simple Java Solution


  • 1

    Detail Explanation: https://briangordon.github.io/2014/08/the-skyline-problem.html

    1. Divide the node into two parts: startNode and endNode.
    2. Sort nodes based on position, height and whether it is startNode.
    • same position: compare whether they are both startNode or both endNode, if they have same status, compared by their height; if not, startNode first, then endNode.

    • different position: the one has smaller position goes first.

    3.Using heap to keep the maximum height of outline. Look through all elements of edges.
    If it's a startNode, check whether the heap is empty or the maximum height is less than the node's height. if it's true, then this is a key point, store it in the result list.
    If it's a endNode, remove the node's height from heap. if heap is empty now, then this is the key point that the outline reaches the horizon. If heap is not empty, compare the new maximum height with node's height to check wether it's a key point.
    Code:

    class Edge {
            int pos;
            int height;
            boolean isStart;
            
        public Edge(int pos, int height, boolean isStart) {
              this.pos = pos;
              this.height = height;
              this.isStart = isStart;
            }
          } 
        class EdgeComparator implements Comparator<Edge> {
            @Override
            public int compare(Edge arg1, Edge arg2) {
              Edge l1 = (Edge) arg1;
              Edge l2 = (Edge) arg2;
              if (l1.pos != l2.pos)
                return compareInteger(l1.pos, l2.pos);
              if (l1.isStart && l2.isStart) {
                return compareInteger(l2.height, l1.height);
              }
              if (!l1.isStart && !l2.isStart) {
                return compareInteger(l1.height, l2.height);
              }
              return l1.isStart ? -1 : 1;
            }
        
            int compareInteger(int a, int b) {
              return a <= b ? -1 : 1;
            }
        }
        public List<int[]> getSkyline(int[][] buildings) {
            List<int[]> res = new ArrayList<int[]>();
            if(buildings==null||buildings.length==0)    return res;
            List<Edge> edges = new ArrayList<Edge>();
            for(int[] building:buildings){
                edges.add(new Edge(building[0],building[2],true));
                edges.add(new Edge(building[1],building[2],false));
            }
            Collections.sort(edges,new EdgeComparator());
            PriorityQueue<Integer> pq = new PriorityQueue<Integer>(10, new Comparator<Integer>(){
                @Override 
                public int compare(Integer o1, Integer o2){
                    return o2-o1;
                }
            });
            for(Edge edge:edges){
                int[] temp = new int[2];
                if(edge.isStart){
                    if(pq.isEmpty()||pq.peek()<edge.height){
                        temp[0] = edge.pos;
                        temp[1] = edge.height;
                        res.add(temp);
                    }
                    pq.add(edge.height);
                }else{
                    pq.remove(edge.height);
                    if(pq.isEmpty()){
                        temp[0] = edge.pos;
                        temp[1] = 0;
                        res.add(temp);
                    }else if(pq.peek()<edge.height){
                        temp[0] = edge.pos;
                        temp[1] = pq.peek();
                        res.add(temp);
                    }
                }
            }
            return res;
        }
    

  • 0
    R

    Thank You for the explanation!


Log in to reply
 

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