贪心算法之活动选择问题

1. 前言

本节内容是贪心算法系列之一：活动选择问题，主要讲解了什么是活动选择问题，如何利用贪心算法解决活动选择问题，给出了活动选择问题的实现伪代码并进行分析，并用 java 语言进行了伪代码实现，帮助大家通过活动选择问题更好的理解贪心算法思想的应用。

2. 什么是活动选择问题？

假设我们现在有一个 n 个活动的集合 S={a₁, a₂, a₃, …a_n}，这些活动需要使用相同一个资源，但是这个资源在某一个时刻只能被一个活动使用，并且每一个活动 a_i 都有一个开始时间 s_i 和结束时间 f_i ，其中 s_i < f_i ，并且开始时间和结束时间都在可以选择的活动时间范围内。这里，如果某个活动 a_i 被选中，则我们可以说活动 a_i 发生在半开时间区间 [ s_i，f_i ) 内，如果两个活动 a_i 和 a_j 满足 [ s_i, f_i ) 和 [ s_j, f_j ) 不重叠，则称它们是兼容的。也就是说，若 s_i >= f_j 或者 s_j >= f_i , 则称 a_i 和 a_j 是相互兼容的，在活动选择问题中，我们希望选出一个最大兼容活动集。

我们考虑现实生活中的一个活动选择问题实例，比如学校里面有一个大的阶梯教室，可以用来上公开课。这里这个阶梯教室就相当于是一个资源，不同的公开课，比如数学课、语文课、英语课等等，这就是一个个活动，并且每节课都有一个开始时间和结束时间，活动选择问题就要求我们选择出所有的可以在阶梯教室中安排的课程，保证选出的课程集合是一个最大的兼容活动集。

接下来，就让我们看看如何利用贪心算法解决活动选择问题。

3. 贪心算法求解活动选择问题

首先，我们假设活动以及按照结束时间的单调递增的顺序排序好，满足： f₁ <= f₂ <= … <= f_i <= … f_n，考虑的活动集合如下：

i	1	2	3	4	5	6	7	8	9	10	11
s_i	1	3	0	5	3	5	6	8	8	2	12
f_i	4	5	6	7	9	9	10	11	12	14	16

回顾一下前一节我们在贪心算法介绍中提到的，能够应用贪心算法求解的问题需要满足两个条件：最优子结构和贪心选择，接下来，我们就具体来看看在活动选择问题中的最优子结构和贪心选择分别是什么。

3.1 最优子结构

我们假设 S_ij 表示在 a_i 结束之后开始，并且在 a_j 开始之前结束的那些活动的集合。我们希望求得 S_ij 的一个最大的相互兼容的活动子集，我们假定 A_ij 就是这样的一个子集，且其中包含活动 a_k 。由于最优解包含活动 a_k ，我们得到两个子问题：寻找 S_ik 中的兼容活动（在 a_i 结束之后开始且 a_k 开始之前结束的那些活动）以及寻找 S_kj 中的兼容活动（在 a_k 结束之后开始且 a_j 开始之前结束的那些活动)。

如上所述，我们假设 c [i, j] 表示集合 S_ij 的最优解的大小，则可以按照这种方式去刻画活动选择问题的最优子结构: c [i, j] = c [i, k] + c [k, j] + 1; 当然，如果我们不知道 S_ij 的最优解包含活动 a_k ，就需要考察 S_ij 中所有活动，寻找哪个活动可以获得最优解，最终结果如下：
图片描述

3.2 贪心选择

假如我们无需求解所有的子问题就可以选择出一个活动加入到最优解，这样可以使得我们省去递归考察所有选择的过程。所以在活动选择问题中，我们只需要考虑一种选择：贪心选择。

对于活动选择问题，什么是贪心选择？直观上说，我们应该选择一个这样的活动，选择它之后剩下的资源可以被尽量多的其他活动选择占用。所以，在这个活动选择问题中，我们选择最早结束的活动，这样剩下来的时间最多，剩下的资源可以供它之后尽量多的活动使用。

3.3 迭代贪心算法

按照上面分析的最优子结构和贪心选择方法，我们可以用迭代的方法去求解活动选择问题，相关伪代码如下：

GreedyActivitySelect(a,s,f):
    //定义活动总数
	n = s.length
    //按照贪心策略，首先选中第一个结束的活动
    A = {a[i]}
    //记录当前选中的活动
    k = 1
    //for循环遍历，按照贪心策略选择活动
    for i=2 to n{
        if s[i] >= f[k]{
            A = A.add(a[i])
            k = i
        }
    }

其中，算法的输入是活动选择集合 a，活动选择问题的开始时间 s 和结束时间 f ，并且已经按照结束时间依次递增的顺序排序好。算法会将选择的活动存入集合 A，最后返回集合 A 作为最终选择的活动集合。

4.JAVA 代码实现

在说明求解钢条切割问题的整个过程之后，接下来，我们看看如何用 java 代码实现钢条切割问题的求解。

import java.util.ArrayList;
import java.util.List;

public class ActivitySelect {

    public static void main(String args[]){
        //活动集合a
        int a[] = {1,2,3,4,5,6,7,8,9,10,11};
        //活动开始时间集合s
        int s[] ={1,3,0,5,3,5,6,8,8,2,12};
        //活动结束集合f
        int f[] ={4,5,6,7,9,9,10,11,12,14,16};
        //活动选择存放集合A
        List<Integer> A =  new ArrayList<>();

        int n = s.length;
        A.add(a[0]);
        int k =0;

        //遍历选择活动
        for (int i=1; i<n; i++){
            if(s[i] >= f[k]){
                A.add(a[i]);
                k = i;
            }
        }

        System.out.println("活动选择问题的选择活动结果为：");
        System.out.println(A);

    }
}

运行结果如下：

活动选择问题的选择活动结果为：
[1, 4, 8, 11]

代码中第 7 行至第 14 行分别初始化活动和对应的开始时间、结束时间以及活动选择过程中存放选择的活动集合，代码的第 16 至 18 行对应着开始的活动选择初始化工作，因为 java 数组的下标从 0 开始，所以这里面我们第一个选择的活动为 a [0]，而不是伪代码中的 a [1]。代码的第 20 行至 26 行 for 循环遍历活动选择，按照贪心选择的方法选择对应的活动，放入最终的结果集 A 中，代码的 28 行 29 行输出相关的活动选择结果。

5. 小结

本节主要学习了利用贪心算法处理活动选择问题，学习本节课程掌握贪心算法解决活动选择问题的流程，知道贪心算法在解决问题时是如何考虑最优子结构及寻找贪心选择，并且可以自己用代码实现活动选择问题的求解。在学习完本节课程之后，我们通过活动选择问题这一实例介绍了贪心算法的实际应用，帮助大家可以更好地理解贪心算法。