設有n個活動的集合E = {1,2,…,n}，其中每個活動都要求使用同一資源，如演講會場等，而在同一時間內只有一個活動能使用這一資源。每個活動i都有一個要求使用該資源的起始時間si和一個結束時間fi,且si < fi 。如果選擇了活動i，則它在半開時間區間[si, fi)內占用資源。若區間[si, fi)與區間[sj, fj)不相交，則稱活動i與活動j是相容的。也就是說，當si >= fj或sj >= fi時，活動i與活動j相容。
使用貪心算法提供了一個簡單漂亮的方法使得盡可能多的活動能兼容地使用公共資源。
例：設待安排的11個活動的開始時間和結束時間如下表所示，按結束時間的非減序排列。
算法分析：
對輸入的活動按其完成時間進行非減序排列，總是選擇最早完成時間的相容活動加入到安排中。該算法的貪心選擇的意義是使剩余的可安排時間段極大化，以便安排盡可能多的活動。
下面是C語言實現（DEV c++4.9.9.2運行通過）
[cpp]
#include<stdio.h>
void greedy(int s[],int f[],int a[],int k);
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 k;
k = sizeof(f)/sizeof(f[0]);
int *a;
a = (int*)malloc(sizeof(int)*k);
greedy(s,f,a,k);
system("PAUSE");
}
/*
* s[]：活動的開始時間
* f[]:活動的結束時間（非降序排列）
* a[]:0或者1，為0表示活動不被安排，1表示活動被安排
* k:活動個數
*/
void greedy(int s[],int f[],int a[],int k)
{
int i;
int j = 0;
for(i=0;i<k;i++)
{
a[i] = 0;//初始所有活動都未被安排
}
a[0] = 1;
printf("第1個活動被安排\n");
int count = 1;
for(i=1;i<k;i++)
{
if(s[i] > f[j])
{
a[i] = 1;
printf("開始%d,結束%d.",s[i],f[i]);
j = i;
count++;
printf("第%d個活動被安排\n",i+1);
}
}
printf("總計%d個活動被安排\n",count);
}
#include<stdio.h>
void greedy(int s[],int f[],int a[],int k);
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 k;
k = sizeof(f)/sizeof(f[0]);
int *a;
a = (int*)malloc(sizeof(int)*k);
greedy(s,f,a,k);
system("PAUSE");
}
/*
* s[]：活動的開始時間
* f[]:活動的結束時間（非降序排列）
* a[]:0或者1，為0表示活動不被安排，1表示活動被安排
* k:活動個數
*/
void greedy(int s[],int f[],int a[],int k)
{
int i;
int j = 0;
for(i=0;i<k;i++)
{
a[i] = 0;//初始所有活動都未被安排
}
a[0] = 1;
printf("第1個活動被安排\n");
int count = 1;
for(i=1;i<k;i++)
{
if(s[i] > f[j])
{
a[i] = 1;
printf("開始%d,結束%d.",s[i],f[i]);
j = i;
count++;
printf("第%d個活動被安排\n",i+1);
}
}
printf("總計%d個活動被安排\n",count);
}
對於活動安排問題，貪心算法總是能求得整體的最優解。
有興趣的朋友們可以用數學歸納法證明。
