贪心——区间问题（一）

一、题目

我们来对比分析2个问题。

区间选点

最大不相交区间数量

先来看下题意——

区间选点

最大不相交区间数量

其实这两道题是一样的。代码都是一样的。
第一个是选择尽量少的点，让所有区间都包含选出的点。
第二个是选择尽量多的区间，让所有区间互不相交。
本质上都是找给定的所有区间中，哪些区间是独立的，跟其他区间毫无衔接关系。

二、解法

一般涉及到多个区间的问题，方法是——按照左端点or右端点对区间进行排序，然后找到一种贪心的策略。
针对上面2道题，则是——

1. 将所有的区间的右端点按照从小到大排序。

2. 维护第一个区间(排序后最左边的区间)的右端点为目标点。

3. 遍历剩下所有区间，如果发现这个点不再连接上其他区间，那么这个当前区间的右端点就算一个答案。然后更新新的目标点(也就是下一个区间的右端点)。

三、C++代码

区间选点

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

typedef pair<int, int> PII;

PII q[N];
int n;
int l, r;

int main()
{
    scanf("%d", &n);
    for(int i = 0; i < n; i ++)
    {
        int l, r;
        scanf("%d%d", &l, &r);
        q[i] = {r, l};
    }
    
    sort(q, q + n);
    
    int res = 1, ed = q[0].first;
    for(int i = 1; i < n; i ++)
        if(ed < q[i].second)
        {
            res ++;
            ed = q[i].first;
        }
    
    cout << res << endl;
    
    return 0;
}

最大不相交区间数量

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

typedef pair<int, int> PII;

PII q[N];
int n;
int l, r;

int main()
{
    scanf("%d", &n);
    for(int i = 0; i < n; i ++)
    {
        int l, r;
        scanf("%d%d", &l, &r);
        q[i] = {r, l};
    }
    sort(q, q + n);
    
    int res = 1, ed = q[0].first;
    for(int i = 1; i < n; i ++)
        if(ed < q[i].second)
        {
            res ++;
            ed = q[i].first;
        }
    
    cout << res << endl;
    
    return 0;
}