218. 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).

Buildings

Skyline Contour

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

题目翻译

一个城市的天际线是由远处城市中的所有建筑物形成的外部轮廓。 现假设给出城市景观照片(图A)所有建筑物的位置和高度,编写一个程序输出这些建筑物形成的天际线(图B)。

每个建筑物的几何信息用三个整数[Li, Ri, Hi]表示,其中LiRi 分别是第i座建筑物的左右边缘的x轴坐标,Hi 是它的高度。 保证0 ≤ Li, Ri ≤ INT_MAX, 0 < Hi ≤ INT_MAX, 和 Ri - Li > 0。假设所有的建筑物都是位于高度为0纯平面上的矩形。

例如,图A中所有建筑物表示为:[ [2 9 10], [3 7 15], [5 12 12], [15 20 10], [19 24 8] ]

输出是以[ [x1,y1], [x2, y2], [x3, y3], ... ] 为格式的关键点(图B中的红点)的唯一列表。关键点是水平线段的左端点。 请注意,最右边的建筑物的最后一个关键点仅用于标记天际线的终点,并始终具有零高度。 此外,任何两个相邻建筑物之间的地面应被视为天际线轮廓的一部分。

例如,图B中的天际线应该被表示为:[ [2 10], [3 15], [7 12], [12 0], [15 10], [20 8], [24, 0] ]

注意:

  • 任何输入列表中的建筑物数量需在 [0, 10000]范围内
  • 输入列表已经按照x轴左端点Li升序排列
  • 输出列表必须按x轴排序
  • 输出天际线中不得有连续的相同高度的水平线。 例如[...[2 3], [4 5], [7 5], [11 5], [12 7]...]是不可接受的。 三条高度为5的线应该在最终输出中合并成一条: [...[2 3], [4 5], [12 7], ...]

解题方案

标签: Divide and Conquer

思路:

  • 步骤1:使用multimap排序所有边界点。对于间隔的起始点,让高度为正, 否则让高度为负
  • 第2步:使用multiset来维护当前的高度集合。如果可满足新的输出起点,则将高度插入到集合中,否则删除高度;当前的最大高度是multiset的back()元素
  • 第3步:根据题目的注意点,从结果集合中删除等高的点

代码:(二进制搜索)

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

        // Step 1:
        multimap<int, int> coords;
        for (const vector<int> & building : buildings) {
            coords.emplace(building[0], building[2]);
            coords.emplace(building[1], -building[2]);
        }
        // Step 2:
        multiset<int> heights = { 0 };
        map<int, int> corners;
        for (const pair<int, int> & p : coords) {
            if (p.second > 0) {
                heights.insert(p.second);
            }
            else {
                heights.erase(heights.find(-p.second));
            }
            int cur_y = *heights.rbegin();
            corners[p.first] = cur_y;
        }
        // Step 3:
        function<bool(pair<int, int> l, pair<int, int> r)> eq2nd = [](pair<int, int> l, pair<int, int> r){ return l.second == r.second;  };
        vector<pair<int, int>> results;
        unique_copy(corners.begin(), corners.end(), back_insert_iterator<vector<pair<int, int>>>(results), eq2nd);
        return results;
    }
};

参考资料

results matching ""

    No results matching ""