A Java solution by iteratively checking the starting and ending points


  • 10
    H
    public class Solution {
    public List<int[]> getSkyline(int[][] buildings) {
        List<int[]> result = new ArrayList<int[]>();
        ArrayList<Point> points = new ArrayList<Point>();
        int n = buildings.length;
        for (int i = 0; i < n; ++i) {
            points.add(new Point(buildings[i][0], buildings[i][2], 0));
            points.add(new Point(buildings[i][1], buildings[i][2], 1));
        }
        Collections.sort(points, new Comparator<Point>() {
            public int compare(Point a, Point b) {
                if (a.val != b.val) return a.val - b.val;
                if (a.flag != b.flag) return a.flag - b.flag;  // Starting point first.
                if (a.flag == 0 && b.flag == 0) return b.height - a.height; // Both starting points, with larger height first.
                return a.height - b.height;     // Both ending points, with smaller height first.
            }
        });
        // Max heap of heights.
        PriorityQueue<Integer> heights = new PriorityQueue<Integer>(9, Collections.reverseOrder());
        for(Point p : points) {
            if (p.flag == 0) {      
            // p is a starting point.
               if (heights.isEmpty() || p.height > heights.peek()) {
                   int[] keyPoint = new int[2];
                   keyPoint[0] = p.val;
                   keyPoint[1] = p.height;
                   result.add(keyPoint);
               }
               heights.add(p.height);
            } else {
                // This is an ending point.
                if (p.height == heights.peek()) {
                    // This happens to be the highest point.
                    heights.poll();
                    if (heights.isEmpty() || p.height > heights.peek()) {
                        int[] keyPoint = new int[2];
                        keyPoint[0] = p.val;
                        keyPoint[1] = heights.isEmpty() ? 0 : heights.peek();
                        result.add(keyPoint);
                    }
                } else {
                    // Does not affect the current height. 
                	heights.remove(p.height);
                }
            }
        }
        return result;
    }
    
    public static class Point {
        int val;
        int height;
        int flag;       // 0 for start and 1 for end.
        Point(int val, int height, int flag) {
            this.val = val;
            this.height = height;
            this.flag = flag;
        }
    }
    

    }


Log in to reply
 

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