贪心算法 -- 区间问题

一、区间选点问题

区间选单个点

问题描述：
数轴上有N个闭区间[Ai, Bi]。取尽量少的点，使得每个区间内都至少有一个点（不同区间内含的点可以是同一个）。

输入
第1行：一个整数N
接下来N行，每行2个整数Ai，Bi

输出
一个整数，表示满足条件的最少点数。

样例输入

【样例输出】

策略分析：

题目要求每个区间都至少有一个点，那么如果存在区间重叠的区域，我们肯定要把点放在重叠的区间最多的区域，同时如果存在小区间包含在大区间中，我们只需要满足小区间即可，同时，每一次选择点的时候，一定是选择该区间的右端点，这样这个点才可能在覆盖当前区间的情况下尽可能的覆盖最多的区间。
因此
1、按照每一个区间的右端点从小到大排序
2、每一次判断当前区间的左端点是否和上一个区间右端点相交，如果相交记录一次，否则要记录两次
注意：每次记录的时候，默认选择区间的右端点

代码

#include <cstdio>
#include <algorithm>
#define MAXN 100000 + 10
using namespace std;
struct node{
    int l, r;
}a[MAXN];
bool cmp(node x, node y) {
    if(x.r == y.r)
        return x.l > y.l;
    return x.r < y.r;
}
int main() {
    int n, now, cnt = 1; // now表示当前选择的点的位置，我们从第二个点开始，因此初始化计数器为1 
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) 
        scanf("%d%d", &a[i].l, &a[i].r);
    sort(a+1, a+1+n, cmp);
    now = a[1].r;
    for(int i = 2; i <= n; i++)
        if(a[i].l > now) { // 如果当前区间和上一个区间不相交，则一定需要设置新的端点 
            now = a[i].r;
            cnt++;
        }
    printf("%d\n", cnt);
    return 0;
}

种树问题（选点）

问题描述：
一条街的一边有几座房子。因为环保原因居民想要在路边种些树。路边的地区被分割成块，并被编号为1…n。每个块大小为一个单位尺寸并最多可种一棵树。每个居民想在门前种些树并指定了三个号码b,e,t。这三个数表示该居民想在b和e之间最少种t棵树。当然b <= e,居民必须保证在指定地区不能种多于地区被分割成块数的树，即要求t <= e-b+1。允许居民想种树的各自区域可以交叉。出于资金短缺的原因,环保部门请你求出能够满足所有居民的要求,需要种树的最少数量。

输入
共n+1行
第1行：输入一个n，表示有n户居民提出要求要在门前种树（1 ≤ n ≤ 100）
后n行：每行输入3个数bi、ei和ti，用空格隔开，分别表示第i户居民想在门前的起点bi到终点ei(包括端点)，想种ti颗树（1 ≤ bi ≤ ei ≤100）

输出
满足n户居民的最少种树量

样例输入

【样例输出】

策略分析：

同样是选点问题，不过变成了选多个点，同样按右端点排序，然后每次种树都从右往左种树，种树之前先扫描这个区间已经种了多少树，然后再种剩下需要种的，使用一个bool数组记录当前的点是否种了树

#include <cstdio> 
#include <algorithm>
#define MAXN 105
bool used[MAXN];
struct zone{
    int start, end, tree;
}a[MAXN];

bool cmp(zone x, zone y) {
    return x.end < y.end;
}
int n, cnt;

int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) 
        scanf("%d%d%d", &a[i].start, &a[i].end, &a[i].tree);
    std::sort(a+1, a+1+n, cmp);
    for(int i = 1; i <= n; i++) {
        int sum = 0;
        for(int j = a[i].start; j <= a[i].end; j++)  // 先扫描当前区间已经种了多少树
            if(used[j])    
                sum++;
        if(sum < a[i].tree)     //如果还需要种树，那么从右端点开始种
            for(int j = a[i].end; j >= a[i].start; j--) 
                if(!used[j]) {
                    used[j] = 1;
                    sum++;
                    cnt++;
                    if(sum >= a[i].tree)
                        break;
                }
    }
    printf("%d\n", cnt);
    return 0;
}

二、不相交区间

问题描述：
数轴上有n个开区间（ai, bi）。选择尽量多个区间，使得这些区间两两没有公共点。
输入
n+1行
第一行：n，表示区间的数量
接下来n行：每行两个数，表示这个区间的起始点和终止点

输出
一个数，最大不相交区间

样例输入

样例输出

策略分析：
首先假设有两个区间x和y，如果x包含在y中，那么我们选择区间时，应该选择x，因为选择x会留下更多的剩余的空间去选择其他的区间
然后按照区间右端点排序，同样定义一个变量设置为当前区间的右端点，每次选择下一个区间的左端点大于当前右端点的区间，更新当前端点即可（由于是按照右端点排序的，那么每次选择下一个区间的时候，右端点都在变大，因此我找到下一个区间左端点大于当前右端点即可更新，这样更新出来的留下来的空间才是最大的）
代码

#include <cstdio>
#include <algorithm>
#define MAXN 55

struct node{
    int start;
    int end;
}a[MAXN];

bool cmp(node x, node y) {
    return x.end < y.end;
}

int main() {
    int n, sum = 1, now;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        scanf("%d%d", &a[i].start, &a[i].end);
    }
    std::sort(a+1, a+1+n, cmp);
    now = a[1].end;
    for(int i = 2; i <= n; i++) {
        if(a[i].start > now) {
            sum++;
            now = a[i].end; 
        }
    }
    printf("%d\n", sum);
    return 0;
}

三、区间覆盖问题

问题描述：
数轴上有n个闭区间[ai,bi]。选择尽量少的区间覆盖一条指定线段[s,t]

输入
n+1行
第一行：一个整数n,表示n个区间，然后是S和T
接下来n行：每行两个整数，表示每个区间的起点和终点
输出
表示最少需要的区间数，如果无解输出No Answer

样例输入

样例输出

策略分析：

区间问题无非就是对区间进行处理，排序筛选，对于区间覆盖来说，要求选择最少的区间数
1、那么首先应该想到，在可能的情况下，应该选择覆盖长度尽可能长的区间，所以如果存在区间包含的情况，应该选择长的区间。
2、在读入时可以对每一个区间进行预处理，帮助做更好的判断，如果读入的区间不在[s,t]范围内，舍去这个无用区间，同时小于s的部分和大于t的部分也要舍去
3、按照左端点从小大大排序（因为要求覆盖，所有应该从左边开始），如果中间有断层或者第一个端点不是s都是无解的情况
代码

#include <cstdio>
#include <algorithm>
#define MAXN 1000005
using namespace std;
struct node {
    int l, r;
}a[MAXN];

bool cmp(node x, node y) {
    if(x.l == y.l)
        return x.r > y.r; 
    return x.l < y.l;
}

int main() {
    int n, s, t, ll, rr, k = 0, cnt = 1, now, i, temp, loc;
    bool flag;
    scanf("%d%d%d", &n, &s, &t);
    for(i = 1; i <= n; i++) {
        scanf("%d%d", &ll, &rr);
        if(rr > s && ll < t) { // 预处理部分
            if(rr > t) rr = t;
            if(ll < s) ll = s;
            a[++k].r = rr;
            a[k].l = ll;
        }
    }
    sort(a+1, a+1+k, cmp);
    if(a[1].l > s) { // 排完序后a[1].l是最小的端点
        printf("No Answer\n");
        return 0;
    }
    now = a[1].r;
    i = 1;
    while(now < t && i <= k) {
        if(a[i].l > now) { // 中间出现断层
            printf("No Answer\n");
            return 0;
        }
        temp = now;
        for(int j = i+1; j <= k; j++) { // 寻找下一个区间最长的点
            if(a[j].l <= now && a[j].r > temp) {
                temp = a[j].r;
                loc = j;
            }
        }
        if(temp == now && temp < t) { // 如果没有找到下一个最长的点并且没有覆盖完的情况下仍然无解
            printf("No Answer\n");
            return 0;            
        }
        i = loc;
        now = temp;
        cnt++;
    }
    printf("%d\n", cnt);
    return 0; 
}

原文链接：本文收藏自CSDN博主「Psycho social」的文章