区间合并 (9/3)

发布时间 2023-09-03 23:20:19作者: 敲代码的6

一、区间合并

1、用sort排序 排 vector的 pair 先排左边再排右边

void merge(vector<PII> &segs){
    vector<PII> res;
    // 左端点排序
    sort(segs.begin(), segs.end());
    // 左右端点初始化,-无穷
    int start = -2e9, end = -2e9;
    for(auto seg: segs){
        if(end < seg.first){
            // 初始的[-无穷,-无穷]区间要跳过,不能装入
            if(start != -2e9) res.push_back({start, end});
            start = seg.first, end = seg.second;
        }
        else end = max(end, seg.second);
    }
    // 有两个作用,1.是防止n为0,把[-无穷,-无穷]压入;2.是压入最后一个(也就是当前)的区间,若n>=1,if可以不要
    if (start != -2e9) res.push_back({start, end});
    //覆盖segs
    segs = res;
}

2、将前几个模板进行了复习