活动选择问题 | 贪心-蒲公英云

活动选择问题 | 贪心

青旅半醒 2023-07-24 03:27 77阅读 0赞

调度共享资源的多个活动，目标是选出一个最大的互相兼容的活动集合。

有一个n个活动的集合 S = {a1, a2, …, an}，每个活动都有一个开始时间si、结束时间fi。时间段不相互重叠的活动是互相兼容的，选出一个最大的兼容活动子集。

一、算法思路

记 $\\bg\_white S\_k=\\left \\\{ a\_i\\epsilon S|s\_i>f\_k \\right \\\}$ 为ak结束后开始的任务集合，且显然有如下定理：

定理1：考虑任意非空子问题 $S\_k$ ，令 $a\_m$ 是 $S\_k$ 中结束时间最早的活动，则 $a\_m$ 在 $S\_k$ 的某个最大兼容活动子集中，

首先要将每个活动的时间段按照结束时间（增序）排序。

直观上，我们每次应该选择这样一个活动，选出它后剩下的资源应该能被尽量多的其他任务所用。故得出贪心选择：每次选择能与子集相容的、最早结束的活动，加入子集。由定理1知：这样的结果必然是一个最大兼容活动子集（不唯一）。

二、算法实现

1、递归实现

#define MAXN
bool isSelected[MAXN] = {false};   //标记是否加入最终的子集
/* 开始时间与结束时间对应存储在数组s、f中（已经按结束时间增序排序好）
 * 在第 k + 1 ~ n个活动间选择:子问题大小为 Sk 
 * 选取结果存储在 isSelected 数组中*/
void RecursiveActivitySelector(int s[], int f[], int k, int n) {
    int m = k + 1;   //开始寻找活动的起点
    while (m <= n && s[m] < f[k])
        m++;   //在范围内找到合适的 m
    if (m <= n) {
        isSelected[m] = true;  //选择第 m个活动
        RecursiveActivitySelector(s, f, m, n);
    }
}

2、递推实现

#define MAXN
bool isSelected[MAXN] = {false};   //标记是否加入最终的子集
/* 开始时间与结束时间对应存储在数组s、f中（已经按结束时间增序排序好）
 * 活动个数为 n
 * 选取结果存储在 isSelected 数组中 */
void GreedyActivitySelector(int s[], int f[], int n) {
    int temp = 1;  //当前选取的活动
    isSelected[temp] = true;
    for(int i = 2; i <=n; i++) {
        /* 找到合适的 */
        if(s[i] >= f[temp]) { 
            temp = i;  //选择
            isSelected[temp] = true;
        }
    }
}

三、其他

有一个n个活动的集合 S = {a1, a2, …, an}，每个活动都有一个开始时间si、结束时间fi。我们需要将它们安排到一些教室，请问最少需要多少个教室？

思路1：贪心算法

   此题就是上面问题的拓展，可以在 S 内选出一个最大兼容活动子集(相当于将他们分配到一间教室)，然后再将这些选择出的活动在 S 中除去，继续选择...直到 S 内活动全都选择完，看分配了多少间教室即可。

思路2：模拟算法

  直接模拟教室的使用情况：将开始时间s与结束时间f放在一起增序排序，且结束时间优先级更高（当时间相同时，结束时间排在开始时间的前面）。依次遍历这个排序好的时间点，遇到开始时间就classroom++，遇到结束时间就classroom--。中间维护一个max\_classroom，记录classroom出现的最大值，即是最终的答案。