活动安排问题来源于实际，无论任何与时间分配有关的问题都要考虑：如何安排来达到占用公共资源最少且花费时间最短的要求。

活动安排问题：设有n个活动的集合C={1,2,…,n}，其中每个活动都要求使用同一个资源(如会议室)，而在同一时间内只能有一个活动使用该资源。每个活动i都有要求使用该资源的起始时间si和结束时间fi，且si<fi。如果选择了活动i使用会议室，那么它在半开区间［si, fi)内占用该资源。如果［si, fi)与［sj,fj)不相交，那么活动i与活动j是相容的。也就是说，当si≥fj或sj≥fi时，活动i与活动j相容。活动安排问题要求在所给的活动集合中选出最大的相容活动子集，也即尽可能选择更多的活动来使用资源。

01、问题分析——贪心策略

仔细审阅活动安排问题的已知条件和目标要求，我们得知：

(1) n个活动的集合C={1,2,…,n}，即由活动编号组成的集合C。

(2) 活动i(i=1,2,…,n)的开始时间si。

(3) 活动i(i=1,2,…,n)的结束时间fi。

(4) 活动i(i=1,2,…,n)使用资源的时间fi-si。

(5) 活动i和活动j相容使用资源的条件：si≥fj或sj≥fi，如图1所示。

■ 图1 活动i和活动j相容示意

6) 满足相容条件的活动子集都是活动安排问题的解，含有活动个数最多的子集就是最优解。

(7) 问题目标：找集合C的最大相容子集，即最优解。

由此，要想实现问题的目标，在满足相容的条件下，我们讨论以下三种贪心策略：

(1) 开始时间早的活动优先安排。

(2) 结束时间早的活动优先安排。

(3) 使用时间短的活动优先安排。

那么，上述三种贪心策略哪个是最优的策略呢？我们看下面一个例子。
【例1】资源安排问题。
4个班级活动争用教室A，它们使用教室A的开始时间和结束时间如表1所示。

表1活动申请表

要求安排尽可能多的班级相容地使用教室A，该如何安排？

按照第一种贪心策略来安排，则1班使用教室A。

按照第二种贪心策略来安排，则2班先使用教室A，然后4班使用教室A。

按照第三种贪心策略来安排，则3班使用教室A。

通过简单对比，我们发现第二种贪心策略：结束时间早的活动优先安排是最佳策略。实际上，通过它们之间的关系：“结束时间=开始时间+使用时间”，我们可以推断：“开始时间越早，使用时间越短，则结束时间越早。”所以，结束时间早的活动优先安排的策略是最好的贪心策略。

02、实例构造

设有10个活动等待安排，这些活动的开始时间和结束时间如表2所示，用贪心算法找出满足目标要求的活动集合。

表2活动编号、开始时间和结束时间

第一步，将活动按照结束时间由小到大排序，排在第一位的2号活动被选择，如表3所示，结束时间为4。

表3第一阶段的贪心选择

第二步，在开始时间大于或等于4的活动集合中贪心选择，选3号活动，如表4所示，结束时间为7。

表4 第二阶段的贪心选择

第三步，在开始时间大于或等于7的活动集合中贪心选择，选7号活动，如表5所示，结束时间为11。

表5 第三阶段的贪心选择

第四步，在开始时间大于或等于11的活动集合中贪心选择，选10号活动，如表6所示，结束时间为14。此时，10号活动是最后一个位置的活动，算法结束。

表6 第四阶段的贪心选择

该实例的解为(0,1,1,0,0,0,1,0,0,1)，即安排的活动集合为{2,3,7,10}。