Day 110, ##, The Skyline Problem

The Skyline 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] ].

Notes:

• The number of buildings in any input list is guaranteed to be in the range [0, 10000].
• The input list is already sorted in ascending order by the left x position Li.
• The output list must be sorted by the x position.
• There must be no consecutive horizontal lines of equal height in the output skyline. For instance, [...[2 3], [4 5], [7 5], [11 5], [12 7]...] is not acceptable; the three lines of height 5 should be merged into one in the final output as such: [...[2 3], [4 5], [12 7], ...]

---------------------------------------------------
Runtime error, C++ vector<> has its maximum size.
Use a heightMap of size INT_MAX

class Solution {
public:
    vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {
        vector<int> heightMap(INT_MAX,0);
        for (int i = 0; i < buildings.size(); i++) {
            int left = buildings[i][0];
            int height = buildings[i][1];
            int right = buildings[i][2];
            
            for (int j = left; j < right; j++) {
                heightMap[j] = max(height,heightMap[j]);
            }
        }
        
        vector<pair<int,int> > rt; 
        int preHeight = 0;
        for (int i = 0; i <= INT_MAX; i++) {
            if (preHeight != heightMap[i]) {
                rt.push_back(make_pair(i,heightMap[i]));
            }
            
            preHeight = heightMap[i];
        }
        
        return rt;
    }
};

方法1：http://www.cnblogs.com/easonliu/p/4531020.html
一句话，找线段。将所有点按照x坐标排序，注意当点重复时，将线段左边点排在线段后边点之前。遍历所有点，遇到左点说明遭遇新线段，插入它的高度在heap。遇到右点说明线段终止，从heap删除该高度（线段）。对比当前跟之前的高度，就能确定线段分界点
因为只需要求的是building的轮廓，所以heap_top保留的是当前x坐标下最高的线段

以下为方法1
处理重复点
c++ 中operator方法的写法
priority_queue不提供中间删除操作
用map而不是set，防止当不同线段的头和尾重复时，确保删除正确

class Solution {
public:
    struct cmp {
        bool operator() (const pair<int, int>& p1, const pair<int, int>& p2) {
            if (p1.first == p2.first) {
                return p1.second < p2.second;
            }
            return p1.first < p2.first;
        }
    };

    vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {
        vector<pair<int,int> > points, rt;
        for (int i = 0; i < buildings.size(); i++) {
            points.push_back(make_pair(buildings[i][0],-buildings[i][2]));
            points.push_back(make_pair(buildings[i][1],buildings[i][2]));
        }
        sort(points.begin(),points.end(),cmp());
        
        priority_queue<int> heightMap;
        heightMap.push(0); // to handle end of a building
        unordered_map<int,int> deleted;
        int pre = 0;
        for (int i = 0; i < points.size(); i++) {
            // left point
            if (points[i].second < 0) {
                heightMap.push(-points[i].second);
            }else {
                // right point
                deleted[points[i].second]++;
                while (!heightMap.empty() && deleted[heightMap.top()] > 0) {
                    deleted[heightMap.top()]--;
                    heightMap.pop();
                }
            }
            
            int cur = heightMap.top();
            if (cur != pre) {
                rt.push_back(make_pair(points[i].first,cur));
                pre = cur;
            }
        }
        
        return rt;
    }
};

方法2：http://www.geeksforgeeks.org/divide-and-conquer-set-7-the-skyline-problem/
basic divide and conquer, 难度在于细节处理上。注意线段的结束点高度设为0

class Solution {
public:
    vector<pair<int,int>> merge(vector<pair<int,int>> left,vector<pair<int,int>> right) {
        vector<pair<int,int>> rt;
        int h1 = 0, h2 = 0;
        int i = 0, j = 0;
        while (i < left.size() && j < right.size()) {
            int x = 0, h = 0;
            if (left[i].first < right[j].first) {
                x = left[i].first;
                h1 = left[i].second;
                h = max(h1,h2);
                i++;
            }else if (left[i].first > right[j].first){
                x = right[j].first;
                h2 = right[j].second;
                h = max(h1,h2);
                j++;
            }else {
                x = left[i].first;
                h1 = left[i].second;
                h2 = right[j].second;
                h = max(h1,h2);
                i++;
                j++;
            }
            if (rt.size() == 0 || rt.back().second != h) {
                rt.push_back(make_pair(x,h));
            }
        }
        
        rt.insert(rt.end(),left.begin() + i,left.end());
        rt.insert(rt.end(),right.begin() + j,right.end());
        return rt;
    }

    vector<pair<int,int>> divide(vector<vector<int>>& buildings, int left,int right) {
        if (left == right) {
            vector<pair<int,int>> rt;
            rt.push_back(make_pair(buildings[left][0],buildings[left][2]));
            rt.push_back(make_pair(buildings[left][1],0));
            return rt;
        }
        int mid = (left + right) / 2;
        vector<pair<int,int>> leftPart = divide(buildings,left,mid);
        vector<pair<int,int>> rightPart = divide(buildings,mid + 1,right);
        return merge(leftPart,rightPart);
    }
    

    vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {
        vector<pair<int, int>> rt;
        if (buildings.size() == 0) return rt;
        return divide(buildings,0,buildings.size() - 1);
    }
};

阅读：https://briangordon.github.io/2014/08/the-skyline-problem.html
Java

class Solution {
    public List<int[]> getSkyline(int[][] buildings) {
        
        List<int[]> points = getSortedPoints(buildings);
        return getSkyline(points);        
    }
    
    private List<int[]> getSkyline(List<int[]> points) {
        PriorityQueue<Integer> que = new PriorityQueue<>((a, b) -> b - a);
        Map<Integer, Integer> map = new HashMap<>();
        List<int[]> rt = new ArrayList<>();
        que.add(0);
        map.put(0, 1);
        
        for (int[] point : points) {
            int x = point[0];
            int height = point[1];
            
            if (height > 0) {
                if (que.peek() < height) {
                    rt.add(new int[]{x, height});
                }
                
                que.add(height);
                map.put(height, map.getOrDefault(height, 0) + 1);
            }else {
                
                map.put(-height, map.get(-height) - 1);
                while (map.get(que.peek()) == 0)  {
                    que.poll();
                }
                
                if (-height > que.peek()) {
                    rt.add(new int[]{x, que.peek()});
                }
                
            }
        }
        
        return rt;
    }
    
    private List<int[]> getSortedPoints(int[][] buildings) {
        List<int[]> points = new ArrayList<>();
        
        for (int[] building : buildings) {
            points.add(new int[]{building[0], building[2]});
            points.add(new int[]{building[1], -building[2]});    
        }
        
        Collections.sort(points, (a, b) -> {
            if (a[0] == b[0]) {
                return b[1] - a[1];
            }
            return a[0] - b[0];
        });
        
        return points;
    }
}