贪心算法之——线段覆盖问题

在线段覆盖这个题型中，简单就举两个例子。 一个是leetcode 435: https://leetcode-cn.com/problems/non-overlapping-intervals/ 一个是洛谷p1803：https://www.luogu.com.cn/problem/P1803

就从洛谷这道题看起吧，标准的线段覆盖问题，题目就已经明确说明：

现在各大 oj 上有 nn 个比赛，每个比赛的开始、结束的时间点是知道的。

yyy 认为，参加越多的比赛，noip 就能考的越好（假的）。

所以，他想知道他最多能参加几个比赛。

由于 yyy 是蒟蒻，如果要参加一个比赛必须善始善终，而且不能同时参加 2 个及以上的比赛。

输入格式
第一行是一个整数 n ，接下来 n 行每行是 2 个整数 ai,bi(ai<bi),，表示比赛开始、结束的时间。

输出格式
一个整数最多参加的比赛数目。

输入输出样例

输入 #1
3
0 2
2 4
1 3

输出 #1
2

线段问题要怎么想？ 来自kkksc03：

在一个数轴上有n条线段，现要选取其中k条线段使得这k条线段两两没有重合部分，问最大的k为多少。 最左边的线段放什么最好？ 显然放右端点最靠左的线段最好，从左向右放，右端点越小妨碍越少 其他线段放置按右端点排序，贪心放置线段，即能放就放

意思就是我们只需要看结束时间，谁结束的越早对右边影响越小，这样得到的选择才会是最优的。这个思路一想到，代码瞬间就很简单的，只需要对结束时间做一个排序，详情见代码吧。

#include<bits/stdc++.h>
using namespace std;
struct test{
    int x;
    int y;
}bai[1000010];

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

int main(){
    int n;
    cin>>n;
    int a[n+1],b[n+1];
    for(int i=1;i<=n;++i){
        cin>>bai[i].x>>bai[i].y;
    }
    sort(bai+1,bai+n+1,cmp);  //对结束时间按照从小到大的顺序排序
    int ans=1; //首先第一个结束的肯定在，先加上它
    int j=1;
    for(int i=2;i<=n;++i){
    //这个就是从第二个线段开始，如果后面一个的起始时间大于上一个的结束时间，那ok，可以加入一个，然后就将j赋值i，接着寻找后面的活动。
        if(bai[i].x>=bai[j].y){ 
            j=i;
            ans++;
        } 
    }
    cout<<ans;
    system("pause");
    return 0;
}

ok了，我们再来看leetcode这题：

给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。

注意:

可以认为区间的终点总是大于它的起点。
区间 [1,2] 和 [2,3] 的边界相互“接触”，但没有相互重叠。
示例 1:

输入: [ [1,2], [2,3], [3,4], [1,3] ]

输出: 1

解释: 移除 [1,3] 后，剩下的区间没有重叠。

乍一看，这题啥意思，你品，你细品，这不还是找最大子段吗，几乎跟上一个题一模一样了。。。 这次我们不用结构体了，换个小小的实现思路：

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        if(intervals.size()==0) return 0;
        int n=intervals.size();
        int first[n];
        int second[n];
        for(int i=0;i<n;++i){
            first[i]=intervals[i][0];
            second[i]=intervals[i][1];
        }
        

        for(int i=0;i<n-1;++i){
            for(int j=0;j<n-i-1;++j){
                if(second[j]>second[j+1]){
                    swap(second[j],second[j+1]);
                    swap(first[j],first[j+1]);
                }
            }
        }
        //一个最简单的冒泡排序好吧，直接将开始时间附着结束时间一起交换位置。
        //下面这个。。。。不用多说了吧

        int ans=1;
        int j=0;
        for(int i=1;i<n;++i){
            if(second[j]<=first[i]){
                ans++;
                j=i;
            }
        }
        return n-ans;
    }
};

总结一下哈，贪心这种题，有了思路，代码很好实现，见的多了，思路就有了，小伙伴们一起加油吧。