---

前言

关于这个活动安排问题的解题思路我第一遍是真的没看懂，所以我就直接看代码了，没想到啊，过一遍代码就直接理解了，真神奇！所以啊，如果第二部分的解题思路没看明白的话就看代码实现吧，代码里也有注释的，哈哈。

---

一、活动安排问题

设有 n 个活动的集合 e = {1,2,3,···,n}，其中每个活动都要求使用同一资源，如演讲、开会、讲座、文艺演出等活动都需要大礼堂这个资源，而在同一时间只有一个活动能使用这一资源。每个活动 i 都有一个要求使用该资源的起始时间 si 和一个结束时间 fi （i为下标），且 si < fi 。请给出一个活动安排方案，使得可能多的活动能使用此资源。

二、解题思路

活动安排问题是用贪心算法有效求解的一个很好的例子。该问题要求高效地安排一系列争用某一公共资源的活动。如果选择了活动 i ，则它在半开时间区间 [si, fi) 内占用资源。若活动 j 的使用区间 [sj, fj) 与区间 [si, fi) 不相交，则称活动 j 与活动 i 是相容的。活动安排问题就是要在所给的活动集合中挑选出最大的相容活动子集合。贪心算法提供了一个简单、漂亮的方法使得尽可能多的活动能兼容地使用公共资源。

用数组 selected 来存储所选择的活动。活动 i 被选择则 selected[i] 的值为 1 ，否则 selected[i] 的值为 0 。变量 j 用来记录最近一次加入到 selected 中的活动。

贪心算法一开始选择活动1，并将 j 初始化为 1。然后依次检查活动 i 是否与当前已选择的所有活动相容。若相容则将活动 i 加入到集合 selected 中，因而取代活动 j 的位置，否则不选择活动 i。

由于输入的活动是以其完成时间升序排列的，所以每次总是选择具有最早完成时间的活动加入集合 selected 中。 从直观上来看，按这种方式选择相容活动就为未安排活动留下了尽可能多的时间。也就是说，该算法的贪心选择的意义是剩余的可安排时间段最大化，以便安排尽可能多的相容活动。当输入的活动已按结束时间按升序排列，这里算法只需 O(n) 的时间来安排 n 个活动，使最多的活动能相容地使用公共资源。

设待安排的活动有11个，所有活动按结束时间升序排列如下图所示：

按照 “在不冲突前提下，具有最早结束时间的活动优先安排” 的贪心选择策略，最终的选择结果如上图的阴影部分所示，选择了4个活动，编号分别是1、4、8、11。

在下面所给出的解决活动安排问题的贪心算法 gpeedyselector 中，各活动的起始时间和结束时间存储于数组 s 和 f 中且按结束时间的升序排列（f1 <= f2 <= ··· <= fn）。如果所给出的活动未按此序排列，可以先对其排序。

三、代码实现

#include <stdio.h>
#define N 100

void greedyselector(int n, int s[], int f[], int selected[]);

int main()
{
	int s[N], f[N]; //s[i],f[i]存储活动 i的开始和结束时间
	int selected[N]; //若活动 i被选择，则selected[i]置1，否则置0
	int n;
	
	printf("请输入活动个数：");
	scanf("%d", &n);
	
	printf("请输入各个活动的开始和结束时间（要求按结束时间升序输入）：\n");
	for (int i = 1; i <= n; i ++)
		scanf("%d%d", &s[i], &f[i]);
		
	greedyselector(n, s, f, selected);
	printf("如下活动被选择：\n");
	for (int i = 1; i <= n; i ++)
		if (selected[i] == 1)
			printf("%d ", i);
			
	printf("\n");
	return 0;
} 

void greedyselector(int n, int s[], int f[], int selected[])
{
	int j = 1; //j记录最近一次加入到a中的活动 
	
	selected[1] = 1; //首先选择活动1 
	for (int i = 2; i <= n; i ++)
		if (s[i] >= f[j]) { //如果活动i与活动j兼容，则选择活动i 
			selected[i] = 1;
			j = i;
		}
		else
			selected[i] = 0;
}

---

总结

在众多的计算机解题策略中，贪心算法可以说是最接近人们的日常思维。但要注意，贪心算法并不从整体最优上加以考虑，所作出的仅是某种意义上的局部最优选择。 使用贪心策略要注意局部最优与全局最优的关系，所以啊，选择当前的局部最优并不一定能推导出问题的全局最优。

贪心策略解题需要解决以下两个问题：

1. 该问题是否适合使用贪心策略求解，也就是该问题是否具有贪心选择性质；
2. 制定贪心策略，以达到问题的最优解或较优解。

要确定一个问题是否适合使用贪心算法解题，必须证明每一步所做的贪心选择最终导致问题的整体最优解。 证明的大致过程为：首先考察问题的一个整体最优解，并证明可修改这个最优解，使其以贪心选择开始，做了贪心选择后，原问题简化为规模更小的类似子问题。然后使用数学归纳法证明通过每一步做贪心选择，最终可以得到问题的整体最优解。