AC Java code beats 96% with detailed explaination


  • 0
    T
        public List<int[]> getSkyline(int[][] buildings) {
            Arrays.sort(buildings, new Comparator<int[]>(){// sort the input list by left ascending, height decending, and right decending
                @Override
                public int compare(int[] b1, int[] b2) {
                    if (Integer.compare(b1[0], b2[0]) != 0) {
                        return Integer.compare(b1[0], b2[0]);
                    } else if (Integer.compare(b2[2], b1[2]) != 0) {
                        return Integer.compare(b2[2], b1[2]);
                    } else {
                        return Integer.compare(b2[1], b1[1]);
                    }
                }
            });
            
            List<int[]> res = new LinkedList<>();
            LinkedList<Integer> list = new LinkedList<>();
            /**
             * we define the following:
             * 1. connected buildings - two buildings that have intersection/common area on the graph. 
             * 2. list of connected buildings - a list of buildings that are either connected or connected through its connected buildings
             *                                  a single building can also be treated as a list of connected building
             * 3. covered building - a building, whose li is greater than the left most li of a list of building and 
             *                       and the ri smaller than the right most ri of the list 
             *                       and hi are smaller than the minimum hi of building
             * TODO: maintain a list of connected buildings that is ordered by building height decending.
             *       when adding buildings to the list, add the new building into the right position and remove new covered building
             */
            outter: for (int i = 0; i < buildings.length; i++) {
                int[] building = buildings[i];
                if (list.isEmpty()) {// if current list is empty, record left corner and and to list
                    res.add(new int[]{building[0], building[2]});
                    list.add(i);
                } else {
                    // record and remove buildings whose right coordinate is smaller than new building's left
                    // thes building are not affected by the new building
                    while (!list.isEmpty() && buildings[list.get(0)][1] < building[0]) {
                        pollAndRecord(list, buildings, res);
                    }
                    if (list.isEmpty() || building[2] > buildings[list.get(0)][2]) {// if new building higher than current highest, add to front
                        res.add(new int[]{building[0], building[2]});
                        list.add(0, i);
                        while (list.size() > 1 && buildings[list.get(1)][1] <= building[1]) {// remove covered building
                            list.remove(1);
                        }
                    } else if (building[2] == buildings[list.get(0)][2]) {    
                        if (building[1] <= buildings[list.get(0)][1]) {// the new building is a covered building
                            continue;
                        } else {
                            list.add(0, i);
                            while (list.size() > 1 && buildings[list.get(1)][1] <= building[1]) {// remove covered building
                                list.remove(1);
                            }
                        }
                    } else {
                        for (int k = 0; k < list.size(); k++) {
                            if (buildings[list.get(k)][2] > building[2]) {
                                if (buildings[list.get(k)][1] >= building[1]) {// the new building is a covered building, skip it
                                    continue outter;
                                } else {
                                    continue;
                                }
                            } else if (buildings[list.get(k)][2] == building[2] && buildings[list.get(k)][1] >= building[1]) {
                                continue outter;// the new building is a covered building, skip it
                            } else {// finded the correct place
                                list.add(k, i);
                                k++;
                                while (list.size() > k && buildings[list.get(k)][1] <= building[1]) {
                                    list.remove(k);
                                }
                                continue outter;
                            }
                        }
                        if (buildings[list.getLast()][2] > building[2] && buildings[list.getLast()][1] < building[1]) {
                            list.add(i);// add to the end of the list
                        }
                    }
                }
            }
            while (!list.isEmpty()) {
                pollAndRecord(list, buildings, res);
            }
            return res;
        }
        
        private void pollAndRecord(LinkedList<Integer> list, int[][] buildings, List<int[]> res) {
            if (list.isEmpty()) {
                return;
            }
            int i = list.poll();
            int x = buildings[i][1];
            int y = list.isEmpty() ? 0 : buildings[list.peek()][2];
            res.add(new int[]{x, y});
        }
    

Log in to reply
 

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