区间合并

步骤：

1. 将区间按照左端点进行排序
2. 循环判断，如果下一个区间的左端点小于（等于）当前区间的右端点时则可以合并，并更新右端点的最大值
3. 如果下一个区间的左端点大于当前区间的右端点时则不可以合并，则更新右端点的最大值为下一个区间的右端点

核心代码：

//t代表有人挤奶牛的区间的集合，f代表没有挤奶牛的区间的集合
//初始化
    LL maxr = a[1].r;
    t[++num_t] = a[1];

//循环遍历
    for(int i=1;i<=n-1;i++){
        if(a[i+1].l <= maxr){
            maxr = max(maxr,a[i+1].r);
            t[num_t].r = maxr;
        }
        else{
            f[++num_f] = {t[num_t].r , a[i+1].l}; //老区间的r和新区间的l
            t[++num_t] = a[i+1];
            maxr = a[i+1].r;
            // cnt++; 区间个数
        }
    }

求区间合并之后区间的总个数

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;
typedef long long LL;

int n,cnt=1;
struct node{
    LL l,r;
}a[N],ans[N];
//左端点从小到大排列
bool cmd(node a, node b){
    return a.l < b.l;
}
int main(){
    cin >> n;
    for(int i=1;i<=n;i++){
        int l,r;
        cin >> l >> r;
        a[i] = {l,r};
    }
    sort(a+1,a+n+1,cmd);
    //从第二个区间开始判断
    LL maxr = a[1].r;
    for(int i=1;i<=n-1;i++){
        if(a[i+1].l <= maxr){
            maxr = max(maxr,a[i+1].r);
        }
        else{
            cnt++;
            maxr = a[i+1].r;
        }
    }
    cout << cnt;
    return 0;
}

练习题

挤奶牛

求区间合并后各个区间的范围

#include <bits/stdc++.h>

using namespace std;

const int N = 1e4+10;
typedef long long LL;

int n;
LL num_t,num_f,max_t,max_f;
struct node{
    LL l,r;
}a[N],t[N],f[N]; //t代表有人挤奶牛的区间的集合，f代表没有挤奶牛的区间的集合

bool cmd(node a,node b){
    return a.l < b.l;
}

int main(){
    cin >> n;
    for(int i=1;i<=n;i++){
        cin >> a[i].l >> a[i].r;
    }
    sort(a+1,a+n+1,cmd);
    LL maxr = a[1].r;
    t[++num_t] = a[1];
    
    for(int i=1;i<=n-1;i++){
        if(a[i+1].l <= maxr){
            maxr = max(maxr,a[i+1].r);
            t[num_t].r = maxr;
        }
        else{
            f[++num_f] = {t[num_t].r , a[i+1].l}; //老区间的r和新区间的l
            t[++num_t] = a[i+1];
            maxr = a[i+1].r;
            // cnt++; 区间个数
        }
    }
    for(int i=1;i<=num_t;i++){
        // cout << t[i].l << " " << t[i].r << "\n";
        max_t = max(max_t,t[i].r-t[i].l);
    }
    for(int i=1;i<=num_f;i++){
        // cout << f[i].l << " " << f[i].r << "\n";
        max_f = max(max_f,f[i].r-f[i].l);
    }
    cout << max_t << " " << max_f;
    return 0;
}