贪心法 活动安排问题

【问题描述】: 设有 $n$n个活动的集合$E = {1, 2, ⋯, n}$E=1,2,⋯,n，其中每个活动都要求使用同一资源(如演讲会场) ，而在同一时间内只有一个活动能使用这一资源。每个活动 $i$i 都有一个要求使用该资源的起始时间 $s_i$si​ 和一个结束时间 $f_i$fi​ , 且 $s_i &lt; f_i$si​<fi​ 。如果选择了活动 , 则它在半开时间区间$[ s_i , f_i )$[si​,fi​)内占用资源。若区间$[ s_i , f_i )$[si​,fi​)与区间$[ s_j , f_j )$[sj​,fj​)不相交, 则称活动 $i $与活动 $j $是相容的。也就是说, 当 $s_i \geq f_j$si​≥fj​或者$s_j \geq f_i$sj​≥fi​时, 活动 $i$i 与活动 $j$j 相容。(也就是说一个活动必须在另一个活动结束之后才能开始) 活动安排问题要求在所给的活动集合中选出最大的相容活动子集。

贪心策略是 选择最早结束时间，以便使得下一个活动尽早开始，这种贪心策略的母的是使得剩余时间段极大化，从而安排尽可能多的相容活动。将$n$n个活动按照结束时间非减序排列。这样而来贪心选择时取当前活动集合中结束时间最早的活动就归结为取当前活动集合中排在最前面的活动。

每当选择了一个活动加入了解集合中，就要判断相应的其他活动是否与之相容。如果不相容则可以直接舍弃。在符合相容条件的解中继续选择具有最早结束时间的解。以此类推，即可得出相应的解集合。

首先选择具有最早结束时间的活动1，然后根据相容条件即可排除活动2和活动3，再选择剩下集合中的具有最早开始时间的活动4。

【算法分析】将各个活动按照结束时间从小到大排序的时间复杂度为$O(nlogn)$O(nlogn)，第四步中依次考察每一个活动，其时间代价为$O(n)$O(n)，因此算法的时间复杂度为$ O(nlogn)$

【算法实现】假设个活动的起始时间和结束时间存储在数组$s[n]$s[n]和$f[n]$f[n]中且按照结束时间非减序排列。数组$B[n]$B[n]存储活动的安排信息，若活动可以安排则$B[i] = 1$B[i]=1

#include <iostream>
using namespace std;
const int N = 11;
/*
 * s: 起始时间
 * f: 结束时间
 * B: 选中与否标记
 * n: 记录的个数
 */
int ActiveManage(int s[], int f[], int B[], int n)
{
	B[0] = 1;	//安排第一个活动，因为之前已经按照f非减序排列了
	int j = 0;
	int cnt = 1; // 计数
	for(int i=1; i<n; i++)	//依次考察后面的情况
	{
		if(s[i] >= f[j]) // 后面活动的开始时间小于当前活动的结束时间，即符合条件
		{
			B[i] = 1; 	// 加入解集合中
			j = i; 		// 考虑之后的活动
			++cnt;
		}
		else
		{
			B[i] = 0;
		}
	}
	return cnt;
}

int main()
{
	int s[] = {1, 3, 0, 5, 3, 5, 6, 8, 8, 2, 12};
	int f[] = {4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14};
	int B[N] = {0};
	int cnt = ActiveManage(s, f, B, N);
	cout << "解向量：";
	for(int i=0; i<N; i++)
	{
		cout << B[i] << " ";
	}
	cout << endl;
	cout << "选择的活动个数：" << cnt << endl;
	return 0;
}

可见与推测的结果相一致，最后选择的是$\{1, 4, 8, 11\}${1,4,8,11}这4个活动。