2 Java Solutions, one of which is short and fast; the other is easy to understand


  • 2
    M

    Solution 1, referring this post.
    Complexity: O(nlogn) time, O(n) space

        public List<int[]> getSkyline(int[][] buildings) {
            List<int[]> outline = new ArrayList<>();
            List<int[]> edges = new ArrayList<>();
            for (int[] b : buildings) {
                edges.add(new int[]{b[0], -b[2]});
                edges.add(new int[]{b[1], b[2]});
            }
            Collections.sort(edges, (int[] b1, int[] b2) -> {
                if (b1[0] != b2[0]) return b1[0] - b2[0];
                return b1[1] - b2[1];
            });
            TreeMap<Integer, Integer> q = new TreeMap<>(Collections.reverseOrder());
            int preH = 0;
            q.put(0, 1);
            for (int[] e : edges) {
                if (e[1] < 0) q.put(-e[1], q.getOrDefault(-e[1], 0) + 1);
                else {
                    if (q.get(e[1]) == 1) q.remove(e[1]);
                    else q.put(e[1], q.get(e[1]) - 1);
                }
                int newH = q.firstKey();
                if (newH != preH) {
                    outline.add(new int[]{e[0], newH});
                    preH = newH;
                }
            }
            return outline;
        }
    

    Another solution, which is longer but more straightforward in algorithm:
    Complexity: O(n^2) time (due to the O(n) time cost of PriorityQueue.remove()), O(n) space. The time cost can be reduced to O(nlogn) by replacing PriorityQueue with TreeMap. However I keep using PriorityQueue to make this solution easy to understand.

    private class Edge implements Comparable<Edge> {
            int x, h;
            Boolean isLeft;
            public Edge(int x, int h, Boolean isLeft) {
                this.x = x;
                this.h = h;
                this.isLeft = isLeft;
            }
            @Override
            public int compareTo(Edge e) {
                if (x != e.x) return x - e.x;
                if (isLeft != e.isLeft) return e.isLeft.compareTo(isLeft);
                if (isLeft) return e.h - h;
                else return h - e.h;
            }
        }
        public List<int[]> getSkyline(int[][] buildings) {
            List<int[]> outline = new ArrayList<>();
            if (buildings == null || buildings.length == 0) return outline;
            Map<Edge, Edge> lefts = new HashMap<>();
            List<Edge> edges = new ArrayList<>();
            for (int i = 0; i < buildings.length; ++i) {
                int[] b = buildings[i];
                Edge left = new Edge(b[0], b[2], true);
                Edge right = new Edge(b[1], b[2], false);
                lefts.put(right, left);
                edges.add(left);
                edges.add(right);
            }
            Collections.sort(edges);
            
            Queue<Edge> q = new PriorityQueue<>(2 * buildings.length, (Edge e1, Edge e2) -> e2.h - e1.h);
            for (Edge edge : edges) {
                int preH = 0;
                if (q.size() > 0) preH = q.peek().h;
                if (!edge.isLeft) q.remove(lefts.get(edge));
                else q.offer(edge);
                int newH = 0;
                if (q.size() > 0) newH = q.peek().h;
                if (newH != preH) outline.add(new int[]{edge.x, newH});
            }
            return outline;
        }
    

Log in to reply
 

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