贪心问题中的一大类别：区间问题

457

2022.05.14

发布于未知归属地

简介

区间问题是贪心中的常出现的一个问题，有些问题看似和区间问题无关，经过一些转换之后也可以变成区间问题
而对于这类问题，是有模板的，因此熟练掌握常见的几种区间问题的思路和代码模板，还是有很大的必要性的。

区间合并

这类问题较为简单，就不做过多叙述，思路就是，对要合并的所有区间进行左端点从小到大排序，如果前一个区间和后一个区间可以合并，则一定有：前一个区间的右端点>=后一个区间的左端点。
因此遍历排序好的区间集合，按照上述思路遍历整个区间集合即可。
代码模板如下:

typedef pair<int,int>PII
void merge(vector<PII> &segs)
{
    vector<PII> res;

    sort(segs.begin(), segs.end());     //pair<int,int>排序优先左端点

    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;
}

模板例题
合并区间

区间覆盖

题目：给定 $N$ 个闭区间 $[a_{i}, b_{i}]$ 问是否能使用这 $N$ 个区间，来将目标区间[start,end]覆盖，如果可以，返回所需要区间的最小数目，如果不可以，返回-1。
输入样例

输出样例

要合并目标区间[1,5] 由所给的区间可知可选择[-1,3] [3,5]两个区间，因此最小选择的区间数目为2
我们知道我们要想合并一个区间，那么我们选择的第一个区间的左端点 $l$ 必定有: $l <= s t a r t$
那如何使得我们所用的区间数最少呢？贪心的思想就是:在所有满足 $l <= s t a r t$ 的区间中，选择一个右端点最大的区间，这样就会尽可能减少我们所使用的区间数量，然后我们选择了第一个区间 $[l, r]$ 覆盖了目标区间[start,r]的部分，因此接下来只需要覆盖[r,end]部分即可，这个时候选择区间就变成在所有满足 $l <= r$ 的区间中，选择一个右端点最大的区间，以此类推，直到完全覆盖区间。
上述题目需要写输入输出，因此附上完整代码，该代码的核心部分可以直接当模板使用:

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef pair<int,int>PII;
vector<PII>arr;
bool mycompare(PII &p1,PII &p2)
{
    return p1.first<p2.first;
}
int main()
{
    int st,ed,n;
    cin>>st>>ed>>n;
    int l,r;
    for(int i=0;i<n;i++)
    {
        cin>>l>>r;
        arr.push_back({l,r});
    }
    bool flag=false;
    int res=0;
    sort(arr.begin(),arr.end(),mycompare);
    for(int i=0;i<n;i++)
    {
        int j=i;r=-2e9;
        while(j<n&&arr[j].first<=st)
        {
            r=max(arr[j].second,r);
            j++;
        }
        if(r<st)
        {
            res=-1;
            break;
        }
        res++;
        if(r>=ed)
        {
            flag=true;
            break;
        }
        st=r;i=j-1;
    }
    if(!flag) res=-1;
    cout<<res<<endl;
    return 0;
}

模板例题:
跳跃游戏
 跳跃游戏II
这两道题我之前写了题解
跳跃游戏题解
 跳跃游戏II题解
虽然这道题可以不用这种思路去解决，尤其是跳跃游戏这道题，有比这个更简单的解决方式，但是大家会发现这两道题的代码基本上完全一致，II只多了一个维护res变量的操作。因此，熟练掌握一些模板，对于做算法题还是很有帮助的。

最大不相交区间数量

题目：给定 $N$ 个闭区间 $[a_{i}, b_{i}]$ ,请你在数轴上选择若干区间，使得选中的区间之间互不相交（包括端点）
输出可选取区间的最大数量。
输入样例

输出样例

这道题其实可以使用合并区间的做法，对区间按照左端点进行排序，最后统计出合并的区间数即可(合并后的每个区间之间都是互不相交的)在这里我们就不讨论合并区间的做法了
我们看能否对区间右端点进行排序，来做这道题
其实这道题等价于区间选点问题：
给定 $N$ 个闭区间 $[a_{i}, b_{i}]$ ，请你在数轴上选择尽量少的点，使得每个区间内至少包含一个选出的点。输出选择的点的最小数量。
为什么可以这样等价呢？因为如果想要选最少的点，那么如果两个或多个区间有交集，一定是选择交集的点，比如样例中[2,4],[3,5]有交集，因此一定是取[2,4],[3,5]中交集的点，那么对于这道题而言，就是说[2,4],[3,5]这两个区间我只能选一个(选了另一个就不能保证区间之间互不相交了)
因此我们可以对右端点从小到大进行排序
首先选择第一个区间的右端点作为分界线，如果第一个区间的右端点小于第二个区间的左端点，说明两个区间没有交集，因此更新计数变量res,并且将分界线更新为第二个区间的右端点的值，最后输出res的值即可。
完整代码如下：

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef pair<int,int>PII;
vector<PII>num;
int n;
bool mycompare(PII &p1,PII &p2){
    return p1.second<p2.second;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin>>n;
    int l,r;
    for(int i=0;i<n;i++)
    {
        cin>>l>>r;
        num.push_back({l,r});
    }
    sort(num.begin(),num.end(),mycompare);
    l=r=-2e9;
    int res=0;
    for(auto item:num)
    {
        if(r<item.first)
        {
            res++;
            r=item.second;
        }
    }
    cout<<res<<endl;
}

模板例题
用最少数量的箭引爆气球
 无重叠区间
第一道题可以等价为区间选点问题，第二道题就是最大不相交区间数量问题。