[编程笔记]-Interval_Problem(Greedy)区间问题（贪心）

前言

鉴于这篇博客目的，我们就挑一些代码量短但是思维难度不低的问题讲。

没错，和DP一样，因为没有具体的套路模板，就直接上例题了。

这篇算作一个大整合，整合了大部分贪心结局的区间问题。

例题

区间选点

原题链接
贪心嘛，就是要贪心一点，想一个最贪心的算法。

对于每一个区间，如果不用选，那最好；要是要选，那就直接选最右边的点。（记得按右端点从小到大排序）

只要排好了序，每次都选最右边，能覆盖的区间一定是最多的。

#include<bits/stdc++.h>
using namespace std;

const int N=1e5+5;

struct qj{
    int a,b;
}qs[N];
int n;

bool cmp(qj a,qj b){
    return a.b<b.b;
}

int ans;

int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>qs[i].a>>qs[i].b;
    }
    sort(qs+1,qs+1+n,cmp);
    int ed=INT_MIN;
    for(int i=1;i<=n;i++){
        if(qs[i].a>ed){
            ed=qs[i].b;
            ans++;
        }
    }
    cout<<ans;
    return 0;
}

最大不相交区间数量

原题链接
题目不一样，但是做法和上面那道一模一样。

有多一模一样？

我直接把代码复制过来了hhh

还是讲一下原理吧。

要是区间有重合，肯定就不能选了。否则，能选。就这样。完了。

#include<bits/stdc++.h>
using namespace std;

const int N=1e5+5;

struct qj{
    int a,b;
}qs[N];
int n;

bool cmp(qj a,qj b){
    return a.b<b.b;
}

int ans;

int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>qs[i].a>>qs[i].b;
    }
    sort(qs+1,qs+1+n,cmp);
    int ed=INT_MIN;
    for(int i=1;i<=n;i++){
        if(qs[i].a>ed){
            ed=qs[i].b;
            ans++;
        }
    }
    cout<<ans;
    return 0;
}

区间分组

原题链接

1. 把所有区间按左端点排好序。
2. 从前往后遍历每个区间：
   • 若可以放入现有的组，放进去。
   • 反之，就开一个新组，然后放进去。
     判断能不能放进一个组，其实就是看当前区间左端点是不是在那个组最右边的右端点右边。

更简单的，我们只需要维护最小的组右端点，每次和它判断即可。那么毫无疑问，直接用小根堆解决。

#include<bits/stdc++.h>
using namespace std;

const int N=1e5+5;

struct qj{
    int a,b;
}qs[N];
int n;

bool cmp(qj a,qj b){
    return a.a<b.a;
}

priority_queue<int, vector<int>, greater<int> > pq;

int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>qs[i].a>>qs[i].b;
    }
    sort(qs+1,qs+1+n,cmp);
    for(int i=1;i<=n;i++){
        if(pq.empty()||pq.top()>=qs[i].a)pq.push(qs[i].b);
        else{
            int t=pq.top();
            pq.pop();
            pq.push(qs[i].b);
        }
    }
    cout<<pq.size();
    return 0;
}

区间覆盖

原题链接

1. 左端点排序
2. 从前往后枚举每个区间，在所有能覆盖当前左边界的区间中，选一个右端点最大的区间。然后更新左边界为最大的右端点。（不用+1，因为要覆盖线段，所以端点必须重合）

#include<bits/stdc++.h>
using namespace std;

const int N=1e5+5;

struct qj{
    int l,r;
}qs[N];

int n;
int s,t;
int ans;

bool cmp(qj a,qj b){
    return a.l<b.l; 
}

int main(){
    cin.tie(0);
    cin>>s>>t>>n;
    for(int i=1;i<=n;i++){
        cin>>qs[i].l>>qs[i].r;
    }
    sort(qs+1,qs+1+n,cmp);
    bool suc=false;
    for(int i=1;i<=n;i++){
        int j=i,r=INT_MIN;
        while(qs[j].l<=s&&j<=n){
            r=max(r,qs[j].r);
            j++;
        }
        if(r<s){
            break;
        }
        ans++;
        i=j-1;
        s=r;
        if(s>=t){
            suc=true;
            break;
        }
    }
    if(suc)cout<<ans;
    else cout<<-1;
    return 0;
}

完结撒花o(￣︶￣)o