LeetCode 218. 天际线问题

LeetCode 218. 天际线问题

思路：扫描线 代码：

class Solution {
public:
    vector> getSkyline(vector>& buildings) {
        vector> res;
        vector> points;
        multiset heights;
        for(auto& b:buildings){
            points.push_back({b[0],-b[2]});
            points.push_back({b[1],b[2]});
        }
        sort(points.begin(),points.end());
        heights.insert(0);
        for(auto& p:points){
            int x=p.first,h=abs(p.second);
            if(p.second<0){//左端点
                if(h>*heights.rbegin())
                    res.push_back({x,h});
                heights.insert(h);
            }else{
                heights.erase(heights.find(h));
                if(h>*heights.rbegin())
                    res.push_back({x,*heights.rbegin()});
            }
        }
        return res;

    }
};