218 - 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], ...]

Credits:
Special thanks to @stellari for adding this problem, creating these two awesome images and all test cases.

Hide Tags

Divide and Conquer Heap

不是那么简单的一道题。
刚开始写了一个比较 naïve 的解法，把起点终点对应的高度（终点视为0）放入 map，就得到了所有点的排好序的序列，
然后依次检查每个building是不是被别人的覆盖（在别人的范围内且更矮），是的话用别人的的高度来更新（终点是 0 自然更小）
最后扫描整个map，如果有数值变化的点，就push到结果里，看起来好像挺简单……
这个solution是work的，但是。。。TLE。

去查帖子，果然是有蹊跷，原来期待的解法，是通过维护高度的一个堆，
每次遇到新起点，把它的高度加入到堆里，遇到终点去掉该高度，这样就能始终跟踪当前的最高building高度了。
但是实际实现的时候，用vector + std::make_heap 还是超时，应该是遇到终点的时候，在vector里查找目标高度比较费时间。。。
没招了只能借鉴别人的帖子，用 multiset ，一来这玩意可以接受多个相同的值，二来它内部就是heap，严格 lgn 。
改用 multiset 之后确实通过了，性能还可以。

另外要注意，这个思路在push的时候，起点 push 负数也是个道道，
要是反过来的话，如果同一个坐标点既是终点又是新的起点的话，例如 [[0,3,3],[1,5,3],[2,4,3],[3,7,3]]
就会多insert，两条记录，一条该点 + 高度 0，一条该点加新高度。
原因是排序的时候，会把同样的坐标点的，负数记录放在前面，
如果是反过来，负数表示终点，那就会认为先到终点，再到起点，于是加上两条记录（当然可以再加处理去掉它们……）。

还没仔细查讨论区，回头再琢磨一下，还有没有更好的方法。

class Solution {
public:1··
    vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {

        vector<pair<int, int>> buff;
        for(int ii=0; ii<buildings.size(); ++ii)
        {
            buff.push_back({buildings[ii][0], 0-buildings[ii][2]});
            buff.push_back({buildings[ii][1], buildings[ii][2]});
        }
        sort(buff.begin(), buff.end());

        vector<pair<int, int>> rst;
        int pre=0, cur=0;

#ifdef USE_MY_HEAP
        vector<int> hh;                             //store all effective heights, organized as a heap
        hh.push_back(0);                            //for last result, it always goes to height 0
        make_heap(hh.begin(), hh.end());
#else
        multiset<int> ms;                           //use multiset, which enable multiple same values
        ms.insert(0);                               //for last result, it always goes to height 0
#endif

        for(auto b : buff)
        {
            if(0>b.second)                          //start point of a building
            {
#ifdef USE_MY_HEAP
                hh.push_back(0-b.second);
                push_heap(hh.begin(), hh.end());
#else
                ms.insert(0-b.second);
#endif
            }
            else                                    //end point of a building
            {
#ifdef USE_MY_HEAP
                for(int ii=0; ii<hh.size();)
                {
                    if((b.second) == hh[ii])
                    {
                        hh.erase(hh.begin()+ii);
                        break;
                    }
                    else
                        ii++;
                }
                make_heap(hh.begin(), hh.end());
#else
                ms.erase(ms.find(b.second));
#endif
            }
           
#ifdef USE_MY_HEAP
            cur = hh.front();
#else
            cur = *ms.rbegin();                     //get current max height, in default is min-heap
#endif

            if(pre != cur)
            {
                rst.push_back({b.first, cur});
                pre = cur;
            }
        }
        return rst;
    }

    //------------------------------ timeout solution with map ------------------------------
    vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {
        map<int, int> buf;
   
        for(int ii=0; ii<buildings.size(); ++ii)
            buf[buildings[ii][0]] = buildings[ii][2], buf[buildings[ii][1]] = 0;

        for(int ii=0; ii<buildings.size(); ++ii)
            for(map<int, int>::iterator b=buf.begin(); b!=buf.end(); b++)
                if((b->first)>=buildings[ii][0] &&
                     (b->first)<buildings[ii][1] &&
                        (b->second) < buildings[ii][2])
                    (b->second) = buildings[ii][2];

        int prev=0;
        vector<pair<int, int>> rst;
        for(auto b : buf)
            if(b.second!=prev)
                rst.push_back(make_pair(b.first, b.second)), prev=b.second;

        return rst;
    }
};
828 ms