Java two Methods, TreeMap and Divide&Conquer


  • 1

    Turns out the divide and conquer method is much faster than the popular TreeMap solution.
    TreeMap solution: the idea is to process each left edge and right edge and update the current top. If the current top is different from the previous top we need add a point to the result. Be cautious when two edges have the same x coordinates: left edge should appear earlier than right edge; for two left edges, higher one appears first; for two right edges, lower one appears first.

        public List<int[]> getSkyline(int[][] buildings) {
            int[][] edges = new int[buildings.length*2][2];
            for(int i = 0; i < buildings.length; i++) {
                edges[i*2] = new int[]{buildings[i][0], -buildings[i][2]};
                edges[i*2+1] = new int[]{buildings[i][1], buildings[i][2]};
            }
            Arrays.sort(edges, new Comparator<int[]>() {
                @Override
                public int compare(int[] o1, int[] o2) {
                    if (o1[0] == o2[0]) return o1[1]-o2[1];
                    else return o1[0]-o2[0];
                }
            });
            TreeMap<Integer, Integer> map = new TreeMap<>();
            map.put(0, 1);
            int prevtop = 0;
            LinkedList<int[]> result = new LinkedList<>();
            for (int[] e : edges) {
                if (e[1] < 0) {
                    map.put(-e[1], map.getOrDefault(-e[1], 0)+1);
                } else {
                    int n = map.get(e[1])-1;
                    if (n == 0) map.remove(e[1]);
                    else map.put(e[1], n);
                }
                if (map.lastKey() != prevtop) result.add(new int[]{e[0], map.lastKey()});
                prevtop = map.lastKey();
            }
            return result;
        }
    

    Divide and conquer method: we first get the skylines of the left half and the right half and then merge them together.

        private LinkedList<int[]> merge(LinkedList<int[]> l1, LinkedList<int[]> l2) {
            LinkedList<int[]> result = new LinkedList<>();
            int prevtop = 0, h1 = 0, h2 = 0, x;
            while (!l1.isEmpty() && !l2.isEmpty()) {
                if (l1.peekFirst()[0] < l2.peekFirst()[0]) {
                    int[] e = l1.removeFirst();
                    h1 = e[1];
                    x = e[0];
                } else if (l1.peekFirst()[0] > l2.peekFirst()[0]) {
                    int[] e = l2.removeFirst();
                    h2 = e[1];
                    x = e[0];
                } else {
                    int[] e1 = l1.removeFirst(), e2 = l2.removeFirst();
                    h1 = e1[1];
                    h2 = e2[1];
                    x = e1[0];
                }
                int curtop = Math.max(h1, h2);
                if (curtop != prevtop) result.add(new int[]{x, curtop});
                prevtop = curtop;
            }
            result.addAll(l1);
            result.addAll(l2);
            return result;
        }
        private LinkedList<int[]> helper(int[][] buildings, int start, int end) {
            LinkedList<int[]> result = new LinkedList<>();
            if (start == end) {
                result.add(new int[]{buildings[start][0], buildings[start][2]});
                result.add(new int[]{buildings[start][1], 0});
            } else {
                int mid = start+(end-start)/2;
                result = merge(helper(buildings, start, mid), helper(buildings, mid+1, end));
            }
            return result;
        }
        public List<int[]> getSkyline(int[][] buildings) {
            if (buildings.length == 0) return new LinkedList<>();
            return helper(buildings, 0, buildings.length-1);
        }
    

Log in to reply
 

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