活动选择问题 | 贪心

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

> 调度共享资源的多个活动，目标是选出一个最大的互相兼容的活动集合。
> 
> 有一个n个活动的集合 S = \{a1, a2, ..., an\}，每个活动都有一个开始时间si、结束时间fi。时间段不相互重叠的活动是互相兼容的，选出一个最大的兼容活动子集。

--------------------

### 一、算法思路 ###

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

> 定理1：考虑任意非空子问题![S\_k][S_k]，令![a\_m][a_m]是![S\_k][S_k]中结束时间最早的活动，则![a\_m][a_m]在![S\_k][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出现的最大值，即是最终的答案。

[bg_white S_k_left _ a_i_epsilon S_s_i_f_k _right]: https://private.codecogs.com/gif.latex?%5Cbg_white%20S_k%3D%5Cleft%20%5C%7B%20a_i%5Cepsilon%20S%7Cs_i%3Ef_k%20%5Cright%20%5C%7D
[S_k]: https://private.codecogs.com/gif.latex?S_k
[a_m]: https://private.codecogs.com/gif.latex?a_m