WITH EXPLANATION ACCEPTED SOLUTION IN JAVA


  • 0

    WITH EXPLANATION ACCEPTED SOLUTION
    the whole codes are made of three parts

    1. store the information of each point, we defined a new class "building", which store the position, height and whether it is the start of the building
    2. Sort them in the order of position. When the two points at the same position, sort it in descending order when they all represent end of the buildings, in ascending order when they both represent the start of buildings. When one is start, the other is end, start is supposed to be before the end.
    3. Traverse each building point.
    class building{
        int bound;
        boolean is_start;
        int height;
        building(){
            
        }
        building(int bound, boolean is_start, int height){
            this.bound = bound;
            this.is_start = is_start;
            this.height = height;
        }
    }
    public class Solution {
        public List<int[]> getSkyline(int[][] buildings) {
            building[] show = new building[buildings.length * 2];
            int index = 0;
            List<int[]> result = new ArrayList<int[]>();
            for(int[] each : buildings){
                show[index] = new building();
                show[index].bound = each[0];
                show[index].is_start = true;
                show[index].height = each[2];
                
                show[index + 1] = new building();
                show[index + 1].bound = each[1];
                show[index + 1].is_start = false;
                show[index + 1].height = each[2];
                index += 2;
            }
            Arrays.sort(show, new Comparator<building>(){
                public int compare(building x1, building x2){
                    if(x1.bound != x2.bound){
                        return x1.bound - x2.bound;
                    }else{
                        return -(x1.is_start ? x1.height : - x1.height) + (x2.is_start ? x2.height : - x2.height);
                    }
                }
            } );
            
            int cur_height = 0;
            int pre_height = 0;
            TreeMap<Integer, Integer> queue = new TreeMap<Integer, Integer>();
            queue.put(0 ,1);
            for(building each : show){
                int height = each.height;
                if(each.is_start){
                    if(queue.containsKey(height)){
                        int x = queue.get(height);
                        x++;
                        queue.put(height, x);
                    }else{
                        queue.put(height, 1);
                    }
                }else{
                    if(queue.get(height) == 1){
                        queue.remove(height);
                    }else{
                        int x = queue.get(height);
                        x--;
                        queue.put(height, x);
                    }
                }
                cur_height = queue.lastKey();
                if(cur_height != pre_height){
                    int[] temp = {each.bound, cur_height};
                    result.add(temp);
                    pre_height = cur_height;
                }
            }
            return result;
        }
    }
    
    * list item``````

Log in to reply
 

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