218. 天际线问题/C++

扫描线

vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {
    multiset<pair<int,int>> set;
    vector<vector<int>> res;
    
    for(vector<int>& v:buildings){
        set.insert(make_pair(v[0],-v[2]));//左边的点负数入set
        set.insert(make_pair(v[1],v[2]));//右边的点正数入set
        //以正负数来区分左右，而且multiset有自动排序的功能，对于同一横坐标的高度，越高的越在后面
    }
    
    multiset<int> heights{0};
    vector<int> last{0,0};
    
    for(const pair<int,int>& p:set){
        if(p.second<0)
            heights.insert(-p.second);//左边界，加入该高度
        else
            heights.erase(heights.find(p.second));//右边界，删除高度
        
        auto maxHeight = *heights.rbegin();//最后的高度就是当前最高的高度
        
        if(last[1] != maxHeight){
            last[0] = p.first;
            last[1] = maxHeight;
            res.push_back(last);
        }
    }
    return res;
}