当前位置：网站首页>区间合并板子

区间合并板子

2022-04-22 02:33:00 【Bzdhxs_nt】

时间复杂度 $O (n)$
贪心

using pll = pair<int,int>;
vector<pll> seg;
void merge(){
    
    vector<pll> res;
    int st = -inf,ed = -inf;
    for(auto s:seg){
    

        if(ed < s.first){
    
            if(st!=-inf) res.push_back({
    st,ed});
            st = s.first, ed = s.second;
        }
        else ed = max(ed,s.second);
    }
    if(st != -inf) res.push_back({
    st,ed});
    seg = res;
}