Leetcode每日一题-2021-7-13<天际线问题>(扫描线)

链接：https://leetcode-cn.com/problems/the-skyline-problem/
218. 天际线问题

代码：

class Solution {
public:
    vector<vector<int>> getSkyline(vector<vector<int>>& b) {
        multiset<pair<int,int>> s;
        for(auto i:b){
            s.insert({i[0],-i[2]});
            s.insert({i[1],i[2]});
        }

        multiset<int> h({0});
        vector<vector<int>> ans;
        vector<int> res={0,0};
        for(auto i:s){
            if(i.second<0){
                h.insert(-i.second);
            }
            else {
                h.erase(h.find(i.second));
            }
            int mh=*h.rbegin();
            if(res[1]!=mh){
                res[1]=mh;
                res[0]=i.first;
                ans.push_back(res);
            }
        }
        return ans;
    }
};

Leetcode每日一题-2021-7-13<天际线问题>(扫描线)

原文：https://www.cnblogs.com/abestxun/p/15005721.html