LeetCode 天际线问题

城市的天际线是从远处观看该城市中所有建筑物形成的轮廓的外部轮廓。现在，假设您获得了城市风光照片（图A）上显示的所有建筑物的位置和高度，请编写一个程序以输出由这些建筑物形成的天际线（图B）。

每个建筑物的几何信息用三元组 [Li，Ri，Hi] 表示，其中 Li 和 Ri 分别是第 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], ...]

思路分析：首先遍历buildings，将轮廓描绘出来，放到map容器（将xi与高度进行关联）。然后扫描，将点读出来。

class Solution {
public:
	vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {
		vector<pair<int, int>> result;//用于存储结果
		map<int, int> myMap;//将xi与对应的高度关联
		//第一步：扫描buildings，将轮廓描绘出来
		for (auto building : buildings){
			if (myMap.count(building[0] - 1) == 0){//左边界前
				myMap[building[0] - 1] = 0;
			}
			//将left~right的高度都设为hi building[2]
			for (int xi = building[0]; xi <= building[1]; ++xi){
				myMap[xi] = max(myMap[xi], building[2]);
			}
			if (myMap.count(building[1] + 1) == 0){//右边界后
				myMap[building[1] + 1] = 0;
			}
		}
		//第二步：扫描myMap将点读出来
		map<int, int>::iterator before, after;
		for (map<int, int>::iterator it = myMap.begin(); it != myMap.end(); ++it){
			if (it->second == 0){
				continue;
			}
			before = after = it;
			--before;
            ++after;
            if (after->second == 0){//一个区域的尾部
                result.push_back(make_pair(it->first, 0));
            }
            else if (before->second < it->second){//左边界
                result.push_back(make_pair(it->first, it->second));
            }
            else if (before->second > it->second){//前一个building的右边界
                result.push_back(make_pair(before->first, it->second));
            }
		}
		return result;
	}
};

但是只过了两个测试就报“超时”。。。
下面是另外一种算法实现。

class Solution {
public:
    vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {
        vector<pair<int, int>> h, res;
        multiset<int> m;
        int pre = 0, cur = 0;//分别标记一个building（不包括重叠部分）的前段、后端
        for (auto &a : buildings) {
            h.push_back({a[0], -a[2]});//左边界记负值
            h.push_back({a[1], a[2]});//右边界记正值
        }
        sort(h.begin(), h.end());//按照左边界下标排序
        m.insert(0);//这样在某个没有和其他建筑重叠的右边界上，我们就可以将封闭点存入结果res中
        //然后开始读点
        for (auto &a : h) {
            if (a.second < 0)//左边界
                m.insert(-a.second);//将正高度加入multiset中
            else //右边界
                m.erase(m.find(a.second));
            cur = *m.rbegin();//取出此时集合中最高的高度，即最后一个数字
            if (cur != pre) {
                res.push_back({a.first, cur});
                pre = cur;//更新
            }
        }
        return res;
    }
};