区间贪心总结(8-9日作业)

ren_gao_zu · 2025-08-10 12:04:12 · 个人记录

总结

点覆盖区间问题

例题：D4327 【例6.6】整数区间（来追梦OJ）

思路：

我们先按右端点从小到大排序，然后进行遍历，就会分成两种情况：

情况一：下一个区间的左端点在这个区间的右端点的左边，此时一定有一个点可以覆盖这两个区间。

情况二：下一个区间的左端点在现在的这个区间的右边，这样两个区间独立，无公共区间，只能用两个点。

例题AC code：
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
int n;
struct node{
int l,r;
}a[1000005];
bool cmp(node x,node y){
return x.r<y.r;
}
int ans;
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n;

for(int i=1;i<=n;i++){
    cin>>a[i].l>>a[i].r;
}
sort(a+1,a+n+1,cmp);
int l1=a[1].l,r1=a[1].r;
for(int i=2;i<=n;i++){
    if(r1<=a[i].l){
        r1=max(r1,a[i].r);
    }else {
        ans++;
        r1=a[i].r;
    }
}cout<<ans;
return 0;

}

## 区间和点配对问题：
### 例题：[P2887 [USACO07NOV] Sunscreen G](https://www.luogu.com.cn/problem/P2887)
### 思路：
>先把区间按右端点从小到大排序，点按大小从小到大排序。
>
>我们再遍历所有区间，每次遍历区间的时候遍历所有的点，如果区间和点能配上点（点在区间内），点数量减一，在把内层循环break掉。
### 例题AC code：
```cpp
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
int n,m;
struct node{
    int l,r;
}a[1000005],b[1000005];
bool cmp(node x,node y)
{
    return x.r<y.r; 
}
bool cm1(node x,node y){
    return x.l<y.l;
}
int ans;
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i].l>>a[i].r;
    }
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=m;i++){
        cin>>b[i].l>>b[i].r;
    }
    sort(b+1,b+m+1,cm1);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(b[j].r>0&&b[j].l>=a[i].l&&b[j].l<=a[i].r){
                b[j].r--;
                ans++;
                break;
            }
        }
    }cout<<ans;
    return 0;
}

最大不相交区间数量问题：

选出尽量多的区间，互不重叠。

例题：D4326 【例6.5】活动选择（来追梦OJ）

思路：
按右端点从小到大排序。

维护一个目前的时间
如果此会议可以开，就开更新时间，不能就看下一个会议。

例题AC code：
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
int n;
struct node{
int l,r;
}a[1000005];
bool cmp(node x,node y)
{
return x.r<y.r; 
}
int ans;
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i].l>>a[i].r;
}
sort(a+1,a+n+1,cmp);
int top=-1;
for(int i=1;i<=n;i++){
if(top<=a[i].l){
ans++;
top=a[i].r;
}
}cout<<ans;
return 0;
}
区间覆盖问题

给出若干区间，求总共覆盖的长度。

例题：P1496 火烧赤壁

思路：

按左端点从小到大排序。
然后遍历所有区间，并维护当前区间的右端点。

如果可以，合并区间，更新右端点。

否则新开一个区间并记录上一个区间的答案。

例题AC code:
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=1e5+5;
struct node{
int l,r;
}a[N];
bool cmp(node x,node y){
return x.l<y.l;
}
int n,ans;

signed main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin>>n; for(int i=1;i<=n;i++)cin>>a[i].l>>a[i].r; sort(a+1,a+n+1,cmp); int l1=a[1].l,r1=a[1].r; for(int i=2;i<=n;i++){ if(r1<=a[i].l){ ans+=r1-l1; l1=a[i].l; r1=a[i].r; } else{ r1=max(a[i].r,r1); } }cout<<ans+r1-l1; return 0; }


## 可相交区间分组问题
### 例题：[P10793 『SpOI - R1』Double Champions](https://www.luogu.com.cn/problem/P10793)
### 思路：
>组内区间越多，交集越小。
>
>如果区间本身长度就小于w,则无解。
>
>先按左端点从小到大排序。
>
>遍历所有区间，维护交集的L和R。
>当区间长度小于w,不能在一组，另开一组。
### 例题AC code：
```cpp
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=1e6+5;
int t;
int n,w,ans=1;
struct node{
    int l,r;
}a[N];
bool cmp(node x,node y){
    if(x.l==y.l)return x.r<y.r;
    return x.l<y.l;

}
void solve(){
    ans=1;
    cin>>n>>w;
    bool flag=1;
    for(int i=1;i<=n;i++){
        cin>>a[i].l>>a[i].r;
        if(a[i].r-a[i].l+1<w)flag=0;
    }
    if(w<=0){
        cout<<1<<endl;
        return;
    }
    if(!flag){
        cout<<"No\n";
        return;
    }sort(a+1,a+n+1,cmp);
    int l1=a[1].l,r1=a[1].r;
    for(int i=2;i<=n;i++){
        l1=max(l1,a[i].l);
        r1=min(r1,a[i].r);
        if(r1-l1+1<w){
            ans++;
            l1=a[i].l,r1=a[i].r;
        }
    }
    cout<<ans<<endl;
}
signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}```