• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

区间合并

开发技术 开发技术 2周前 (05-03) 9次浏览

3. 区间合并

原理:区间排序左端点有交集的区间可以合并

struct OI{int l, r;}num[N];

inline int cmp(OI a, OI b){return a.l < b.l;}  //按照左端点排序

sort(num+1, num+1+n,cmp);

void combine(){
    int st = num[1].l, ed = num[1].r;res++; //起始作为一个区间, 所以res起始为 1 个区间
    for(int i = 2; i <= n; i++){
        if(num[i].l <= ed)       // 可以合并成一个区间
            ed = max(ed,num[i].r);
        else
            st = num[i].l, ed = num[i].r, res++;// 不能合并成一个区间
    }
}

程序员灯塔
转载请注明原文链接:区间合并
喜欢 (0)