区间贪心

四种区间贪心问题

1、区间选点

描述：

给定 N 个闭区间 [ai,bi]，请你在数轴上选择尽量少的点，使得每个区间内至少包含一个选出的点。
输出选择的点的最小数量。

核心思路：

​ （1）定义一个pair<int, int>类型的数组，进行所有区间的维护，将所有区间按右端点从小到大进行排序
​ （2）从前往后遍历所有区间，如果当前区间与后一个区间没有交集（即后一个区间的左端点大于前一个区间的右端点），相当于把有交集的区间用一个点进行替代，然后答案 ++，更新新区间的右端点
​ （3）有交集则不用进行任何处理，因为右端点是按照从小到大进行排序的，我们正需要保证右端点是最小的，故当前枚举到的区间右端点就是最小的

代码模板：

   typedef pair<int, int> PII;	//区间维护
   PII e[N];

   bool cmp(PII a, PII b) //自定义右端点排序
   {
       return a.y < b.y;
   }

for (int i = 1; i <= n; i ++) cin >> e[i].x >> e[i].y;//输入区间
   sort(e + 1, e + 1 + n, cmp);//排序
   
   int ed = -0x3f3f3f3f;
   for (int i = 1; i <= n; i ++)	//进行枚举
   {
       if (e[i].x > ed) res ++, ed = e[i].y;
   }

注意：

​ 在区间有交集的时候，一定不要更新右端点了，因为我们需要的就是选定区间中的最小右端点，这与我们按照右端点进行从小到大排序是刚好符合的。

证明：

略

2、最大不相交区间数量

描述：

​ 给定N个区间[a, b]，请你在数轴上选择若干区间，使得选中的区间之间互不相交（包括端点）。输出可选取区间的最大数量。

核心思路：

​ 将所有有交集的区间看作一个区间，因为每次只能选择有交集中的一个，故这样假设没有错，即我们在前往后枚举每个区间的时候，遇到有交集的区间就跳过，只需要在每次遇到没有交集的区间的时候进行统计，步骤如下：

（1）定义一个pair<int, int>类型的数组，进行所有区间的维护，将所有区间按右端点从小到大进行排序
（2）从前往后遍历所有区间，如果当前区间与后一个区间没有交集（即后一个区间的左端点大于前一个区间的右端点），相当于把有交集的区间看作一个区间，然后在遇到没有交集的区间时，答案 ++，更新新区间的右端点
（3）有交集则不用进行任何处理，因为我们将他们看作一个区间

代码实现：

   typedef pair<int, int> PII;	//区间维护
   PII e[N];

   bool cmp(PII a, PII b) //自定义右端点排序
   {
       return a.y < b.y;
   }

for (int i = 1; i <= n; i ++) cin >> e[i].x >> e[i].y;//输入区间
   sort(e + 1, e + 1 + n, cmp);//排序
   
   int ed = -0x3f3f3f3f;
   for (int i = 1; i <= n; i ++)	//进行枚举
   {
       if (e[i].x > ed) res ++, ed = e[i].y;
   }

证明：

略

3、区间分组

描述：

给定N个闭区间[a, b]，请你将这些区间分成若干组，使得每组内部的区间两两之间（包括端点）没有交集，并使组数尽可能小。

核心思路：

​ 我们需要思考，想要将当前区间加入到已有的集合中，则必选满足当前区间与某个集合中的所有区间都没有交集，即当前区间的左端点要大于某个集合的所有右端点，贪心一下，我们只需要维护一个小根堆，存入每个组的最大右端点，在判断能否加入当前组的时候，就与堆顶元素（所有组里最小的最大右区间）步骤如下：

​ （1）先将所有区间按照左端点从小到大排序

​ （2）从前往后处理每一个区间

​ （3）判断是否能放入当前某一个组内：能放的条件是当前一个组都没有或者现有的组中，存在一个组的最大右区间，可以用小根堆的堆顶元素作为边界，大于则可以放入现有组，小于等于则无法放入

​ （4）存在这样的组，就把该区间放入组中，更新当前组的max_r

​ （5）不存在这样的组，就重新创建一个组，将该区间放入

代码模板：

typedef pair<int, int> PII;
PII e[N];

for (int i = 1; i <= n; i ++) cin >> e[i].x >> e[i].y;
    sort(e + 1, e + 1 + n);

    priority_queue<int, vector<int>, greater<int>> heap;
    for (int i = 1; i <= n; i ++)
    {
        if (heap.empty() || e[i].x <= heap.top()) heap.push(e[i].y);
        else
        {
            heap.pop();
            heap.push(e[i].y);
        }
    }
cout << heap.size();

注意：

这里用小根堆（优先队列），进行维护每一个组的所有区间最大右区间，则堆顶就是所有组的最大右区间的最小值，
也就是一个新区间想要加入现有组的条件，即新区间的左端点要大于该条件

证明：

略

4、区间覆盖

描述：

​ 给定N个闭区间[a, b]以及一个线性区间[s, t]，请你选择尽量少的区间，将指定线段区间完全覆盖。

核心思路：

​ （1）按照左端点进行排序

​ （2）用双指针算法线性扫描一下所有区间，每次扫描 找出 能覆盖还未覆盖的区间 的左端点的 所有区间中，右端点最大的区间，将start更新为其左端点。

代码模板：

typedef pair<int, int> PII;	
PII e[N];

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

for (int i = 1; i <= n; i ++) cin >> e[i].x >> e[i].y;	//输入
    sort(e + 1, e + 1 + n, cmp);	//排序
    
    int res = 0;	//答案
    bool flag = false;	//标志位
    for (int i = 1; i <= n; i ++)
    {
        int j = i, r = -2e9;	//获取当前区间，即e[i] ~ ed
        while (j <= n && e[j].x <= st)	//双指针扫描
        {
            r = max(r, e[j].y);
            j ++;
        }
        
        if (r < st) //后面区间无法覆盖，提前结束
        {
            res = -1;
            break;
        }
        
        res ++;	//可以覆盖，所用区间 ++
        
        if (r >= ed) 	//完全覆盖，标志成功，结束扫描
        {
            flag = true;
            break;
        }
        
        st = r;	//更新未扫描区间
        
        i = j - 1;	//由于for循环中i ++,故这里i更新为需要扫描的点j的前一个点
    }
    
    if (!flag) res = -1;
    cout << res;

注意：

​ （1）需要注意的点是几个特判：如果更新后r < st说明剩余区间没有一个区间能够覆盖剩余部分，直接结束扫描，反之则所用的区间 ++；
​ （2）是当前区间的r >= ed，说明需要覆盖的区间已经完全覆盖，标志位设置为true，结束遍历即可。
​ （3）最后根据标志位判断是否覆盖了全部区间。

（4）避免遍历重复的区间，但为什么是i = j - 1，而不是i = j， 因为前j个区间我们已经判断过了，需要判断第j个区间， 但由于for循环结束会i++，如果这里i = j，再算上循环结束的i++， 下一次循环遍历的就会是第j + 1个区间，而导致跳过了第j个区间

证明：

略