城市的天际线是从远处观看该城市中所有建筑物形成的轮廓的外部轮廓。现在，假设您获得了城市风光照片（图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], ...]

　　　　

　　

只考虑每个 building 的左上角和右上角坐标，将所有点按 x 坐标排序，然后开始遍历。

需要一个优先队列来存储遍历坐标的高度，也就是 y 轴坐标。

对于左上角坐标和右上角坐标有不同的处理方式。

遇到左上角坐标，将其 y 坐标加入到优先队列中。

遇到右上角坐标，将其 y 坐标从优先队列中删除，也就是删除了其对应的左上角坐标的 y 值。

最后判断优先队列中的最高高度相对于之前是否更新，如果更新了的话，就将当前的 x 以及更新后的最高高度作为一个坐标加入到最终结果中。

class Solution {
public:
    struct Node {
        int x;  //x坐标
        int y;  //y坐标
    };
    static bool cmp(Node n1,Node n2) {
        //先按x坐标排，x小的在前
        if(n1.x != n2.x) {
            return n1.x < n2.x;   
        }
        //画图举例子，这几种情况难理解
        //如果相等:1、都为左坐标，高的在前(y小)；2、都为右坐标，低的在前先删无变化(y小)；3、一左一右，左在前(左的y为负)
        return n1.y < n2.y;
    }
    
    vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {
        vector<vector<int>> res;
        //先把输入转化成二维坐标形式.(x,y)形式。每个输入buildings有三个值，leftx rightx y。可拆分成2个坐标
        vector<Node> coordinate;
        //左坐标的y值设为负，右坐标值设为正。1区分左右，2排序时妙用。
        for(int i=0;i<buildings.size();i++){
            Node n1,n2;
            n1.x = buildings[i][0];
            n1.y = -buildings[i][2];
            n2.x = buildings[i][1];
            n2.y = buildings[i][2];
            coordinate.push_back(n1);
            coordinate.push_back(n2);
        }
        //将所有的坐标排序
        sort(coordinate.begin(),coordinate.end(),cmp);
        //借助优先队列存高度值(堆):当插入左坐标或者删除右坐标，优先队列有高度值变化，该x与优先队列中y最大值即为一个节点
        // priority_queue<int> p;
        // p.push(0);
        // int preMax = p.top();
        //发现priority_queue没法删除指定值，因为删除右坐标时需要删除其y。引入multiset,也是有序的，最后一个最大
        multiset<int> s;
        s.insert(0);
        int preMax = *s.rbegin();
        int maxCur = *s.rbegin();
        for(int i=0;i<coordinate.size();i++){
            vector<int> cor;
            //左坐标
            if(coordinate[i].y < 0){
                s.insert(-coordinate[i].y);
                maxCur = *s.rbegin();
                if(maxCur > preMax){
                    cor.push_back(coordinate[i].x);
                    cor.push_back(maxCur);
                    res.push_back(cor);
                }
                preMax = maxCur;
            }
            //右坐标:删除
            if(coordinate[i].y > 0){
                multiset<int>::iterator iter = s.find(coordinate[i].y);
                s.erase(iter);
                maxCur = *s.rbegin();
                if(maxCur < preMax){
                    cor.push_back(coordinate[i].x);
                    cor.push_back(maxCur);
                    res.push_back(cor);
                }
                preMax = maxCur;
            }
        }
        return res;
    }
};