区间合并

原理

贪心

模板代码

// 将所有存在交集的区间合并
void merge(vector<PII> &segs)
{
    vector<PII> res;
    sort(segs.begin(), segs.end());
    
    int st = -2e9, ed = -2e9;
    for(auto seg : segs)
    {
        if(ed < seg.first)
        {
            if(st!=-2e9) res.push_back({st, ed});
            st = seg.first, ed = seg.second;
        }
        else ed = max(ed, seg.second);
    }
    if(st!=-2e9) res.push_back({st, ed});
    segs = res;
}

区间合并题目链接

803. 区间合并 - AcWing题库

区间合并代码

#include<iostream>
#include<algorithm>

using namespace std;

typedef pair<int, int> PII;

const int N = 100010;

int n;
vector<PII> segs;

void merge(vector<PII> &segs)
{
    vector<PII> res;
    
    sort(segs.begin(),segs.end());
    
    int st = -2e9, ed = -2e9;
    for(auto seg : segs)
        if (ed < seg.first)
        {
            if(st != -2e9) res.push_back({st, ed});
            st = seg.first, ed = seg.second;
        }
        else
        {
            ed = max(ed, seg.second);    
        }
    if(st!=-2e9) res.push_back({st, ed});
    
    segs = res;
}
int main()
{
    cin >> n;
    
    for(int i=0;i<n;i++)
    {
        int l, r;
        cin>>l>>r;
        
        segs.push_back({l, r});
    }
    merge(segs);
    cout<<segs.size() << endl;
    return 0;
}