Java AC solution with a PriorityQueue beats 95% with picture explanation


  • 1
    W

    The idea is if two building overlaps, then convert these two buildings to two non-overlapping buildings.

    0_1494727181173_IMG_4111.JPG

        public class Building {
            private int left;
            private int right;
            private int height;
            public Building(int[] building) {
                this.left = building[0];
                this.right = building[1];
                this.height = building[2];
            }
        }
    
        public List<int[]> getSkyline(int[][] buildings) {
            List<int[]> res = new ArrayList<>();
            if (buildings.length == 0) return res;
            
            Comparator<Building> comparator = new Comparator<Building>() {
                public int compare(Building b1, Building b2) {
                    if (b1.left == b2.left) {
                        return b2.height - b1.height;
                    }
                    return b1.left - b2.left;
                }
            };
            PriorityQueue<Building> queue = new PriorityQueue(16, comparator);
            for (int[] building : buildings) queue.offer(new Building(building));
            
            Building curr = queue.poll();
            while (!queue.isEmpty()) {
                Building next = queue.poll();
                
                if (next.left == curr.right) {
                    if (next.height == curr.height) {
                        curr.right = next.right;
                    } else {
                        res.add(new int[]{curr.left, curr.height});
                        curr = next;
                    }
                } else if (next.left > curr.right) {
                    res.add(new int[]{curr.left, curr.height});
                    res.add(new int[]{curr.right, 0});
                    curr = next;
                } else {
                    if (curr.left == next.left) {
                        if (next.right > curr.right) {
                            if (next.height == curr.height) {
                                curr = next;
                            } else {
                                next.left = curr.right;
                                queue.offer(next);
                            }
                        }
                    } else {
                        if (next.right >= curr.right) {
                            if (next.height == curr.height) {
                                curr.right = next.right;
                            } else if (next.height > curr.height) {
                                curr.right = next.left;
                                queue.offer(next);
                            } else if (next.right > curr.right) {
                                next.left = curr.right;
                                queue.offer(next);
                            }
                        } else if (next.height > curr.height) {
                            queue.offer(next);
                            queue.offer(new Building(new int[]{next.right, curr.right, curr.height}));
                            curr.right = next.left;
                        }
                    }
                }
            }
            res.add(new int[]{curr.left, curr.height});
            res.add(new int[]{curr.right, 0});
            return res;
        }
    

Log in to reply
 

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