218. The Skyline Problem

Problem:

A city's skyline is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance. Now suppose you are given the locations and height of all the buildings as shown on a cityscape photo (Figure A), write a program to output the skyline formed by these buildings collectively (Figure B).

 

The geometric information of each building is represented by a triplet of integers [Li, Ri, Hi], where Li and Ri are the x coordinates of the left and right edge of the ith building, respectively, and Hi is its height. It is guaranteed that 0 ≤ Li, Ri ≤ INT_MAX, 0 < Hi ≤ INT_MAX, and Ri - Li > 0. You may assume all buildings are perfect rectangles grounded on an absolutely flat surface at height 0.

For instance, the dimensions of all buildings in Figure A are recorded as: [ [2 9 10], [3 7 15], [5 12 12], [15 20 10], [19 24 8] ].

The output is a list of "key points" (red dots in Figure B) in the format of [ [x1,y1], [x2, y2], [x3, y3], ... ] that uniquely defines a skyline. A key point is the left endpoint of a horizontal line segment. Note that the last key point, where the rightmost building ends, is merely used to mark the termination of the skyline, and always has zero height. Also, the ground in between any two adjacent buildings should be considered part of the skyline contour.

For instance, the skyline in Figure B should be represented as:[ [2 10], [3 15], [7 12], [12 0], [15 10], [20 8], [24, 0] ].

Analysis:
6/6/2018 update:
反复刷题真是太重要了，自以为这套题搞懂了。其实完全没有。
If we encounter end pos and its the current highest. We remove it from heap, then the current highest point is less than the previous one. So we add this end point and current height to res as desc requires.

At pos 7 height 15, it changes height from 15 to 12. We add [7, 12]  to res.

Code is more readable with Point class defined.

class Solution {
    class Point {
        int pos;
        int height;
        public Point(int pos, int height){
            this.pos = pos;
            this.height = height;
        }
    }
    
    public List<int[]> getSkyline(int[][] buildings) {
        List<int[]> res = new ArrayList<>();
        List<Point> points = new ArrayList<>();
        for (int[] b: buildings) {
            // b {start, end, height}
            points.add(new Point(b[0], -b[2]));
            points.add(new Point(b[1], b[2]));
        }
        Collections.sort(points, (a, b) -> {
            if (a.pos == b.pos) {
                return a.height - b.height;
            } else {
                return a.pos - b.pos;
            }
        });
        
        PriorityQueue<Integer> heights = new PriorityQueue<>((a, b) -> b - a);
        heights.offer(0);
        int prevHeight = 0;
        for (Point point: points) {
            if (point.height < 0) {
                heights.offer(-point.height);
            } else {
                heights.remove(point.height);
            }
            int curHeight = heights.peek();
            if (curHeight != prevHeight) {
                res.add(new int[]{point.pos, curHeight});
                prevHeight = curHeight;
            }
        }
        
        return res;
    }
    
}

--------------------------------------------------------------------------------------------------------------------------------------------

We can observe that the skyline change at two situations.

1. Beginning of building which is higher than current highest.

2. Ending of building which is the current highest. 

In general, sweeping from left to right, whenever the highest point changes, it's the skyline point. 

Solution:

Add all points (index, height) to list, sort from left to right.  Set building begin point height to minus to distinguish. 

Use a max heap to maintain the max height. Meet begin point add to heap, meet end point remove from heap. If max height changes, add to res. 

class Solution {
    public List<int[]> getSkyline(int[][] buildings) {
        // initial boundries, sort from left to right
        // set left boundries height to -h
        List<int[]> res = new ArrayList<>();
        List<int[]> boundries = new ArrayList<>();
        for (int[] b: buildings) {
            boundries.add(new int[]{b[0], -b[2]});
            boundries.add(new int[]{b[1], b[2]});
        }

        Collections.sort(boundries, (a, b) -> {
            if (a[0] == b[0]) {
                return a[1] - b[1];
            } else {
                return a[0] - b[0];
            }
        });
        
        PriorityQueue<Integer> queue = new PriorityQueue<>((a,b) -> (b - a));
        queue.offer(0);
        int prev = 0;
        for (int[] cur: boundries) {
            if (cur[1] < 0) {
                queue.offer(-cur[1]);
            } else {
                queue.remove(cur[1]);
            }
            int curHeight = queue.peek();
            if (curHeight != prev) {
                res.add(new int[]{cur[0], curHeight});
                prev = curHeight;
            }
        }

        return res;
    }
}