当前位置：网站首页>Interval merging board

Interval merging board

2022-04-22 02:36:00 【Bzdhxs_ nt】

Time complexity $O (n)$
greedy

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;
}