利用貪心算法求解活動安排問題

活動安排問題就是要在所給的活動集合中選出最大的相容活動子集合，是可以用貪心算法有效求解的很好例子。該問題要求高效地安排一系列爭用某一公共資源的活動。貪心算法提供了一個簡單、漂亮的方法使得盡可能多的活動能兼容地使用公共資源。

??? 設(shè)有n個活動的集合E={1,2,…,n}，其中每個活動都要求使用同一資源，如演講會場等，而在同一時間內(nèi)只有一個活動能使用這一資源。每個活動i都有一個要求使用該資源的起始時間si和一個結(jié)束時間fi,且si<fi 。如果選擇了活動i，則它在半開時間區(qū)間[si, fi]內(nèi)占用資源。若區(qū)間[si, fi]與區(qū)間[sj, fj]不相交，則稱活動i與活動j是相容的。也就是說，當(dāng)si≥fj或sj≥fi時，活動i與活動j相容。

????由于輸入的活動以其完成時間的非減序排列，所以算法greedySelector每次總是選擇具有最早完成時間的相容活動加入集合A中。直觀上，按這種方法選擇相容活動為未安排活動留下盡可能多的時間。也就是說，該算法的貪心選擇的意義是使剩余的可安排時間段極大化，以便安排盡可能多的相容活動。

????此算法的效率極高。當(dāng)輸入的活動已按結(jié)束時間的非減序排列，算法只需O(n)的時間安排n個活動，使最多的活動能相容地使用公共資源。如果所給出的活動未按非減序排列，可以用O(nlogn)的時間重排。

例：設(shè)待安排的11個活動的開始時間和結(jié)束時間按結(jié)束時間的非減序排列如下：

?

算法的計算過程如圖所示。圖中每行相應(yīng)于算法的一次迭代。陰影長條表示的活動是已選入集合A的活動，而空白長條表示的活動是當(dāng)前正在檢查相容性的活動。

?

若被檢查的活動i的開始時間Si小于最近選擇的活動j的結(jié)束時間fi，則不選擇活動i，否則選擇活動i加入集合A中。

?????貪心算法并不總能求得問題的整體最優(yōu)解。但對于活動安排問題，貪心算法卻總能求得的整體最優(yōu)解，即它最終所確定的相容活動集合A的規(guī)模最大。這個結(jié)論可以用數(shù)學(xué)歸納法證明。

?

#include#include#includeusing?namespace?std;

typedef?struct{
	int?s;//開始時間
	int?f;//結(jié)束時間
}node;

int?cmp(const?void?*a,?const?void?*b)
{
	return?((node?*)a)->f-((node?*)b)->f;//按結(jié)束時間升序排列
}

void?main()
{
	int?i,?j=0,?n;
	int?count=1;
	node?a[100];	
	cin>>n;
	for(i=0;?i>a[i].s>>a[i].f;

	qsort(a,?n,?sizeof(a[0]),?cmp);

	for(i=1;?ia[j].f)
		{
			j=i;
			count++;
		}
	}

	cout<<count<<endl;
}