活动安排问题
活动安排问题
I.问题描述
设有n个活动的集合E={1, 2, …, n}，其中每个活动都要求使用同一资源，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si
查找每个活动的结束时间，每一次选择时查找具有最早结束时间的相容的活动，先把n个活动按时间的结束时间非减序排列，这样，贪心选择是取当前活动集合中结束时间最早的活动就归结为取当前活动集合中排在最前面的活动。
由于输入的活动以其完成时间的非减序排列，所以该算法GREEDY_SELECTOR每次总是选择具有最早完成时间的相容活动加入集合A中。
直观上，按这种方法选择相容活动为未安排活动留下尽可能多的时间。即贪心算法的贪心选择的意义是使剩余的可安排时间段极大化，以便安排尽可能多的相容活动。 这种贪心算法的效率很高，时间复杂性O(nlogn)。
III.算法描述：
GREEDY_SELECTOR(n, activity)
//结构体数组activity[1..n]
//activity.index：活动的编号
//activity.s：活动的起始时间
//activity.f：活动的结束时间
//activity.select：true，则选择活动；false，不选择活动
SORT(activity) // 按结束时间非减序排列
activity[1].select = true
p = 1
for i=2 to n
if activity[i].s >= activity[p]. f
activity[i].select = true
p = i
else
activity[i].select = false
IV.程序
#include
void sort(int s[],int f[],int n)//把各个活动的起始时间和结束时间按结束时间递增排序 {
int a,b;
int i,j;
for(i=0;i
{
for(j=i+1;j
{
if(f[i]>f[j])
{a=f[i];f[i]=f[j];f[j]=a;
b=s[i];s[i]=s[j];s[j]=b;}
}
}
}
int activemanage(int s[],int f[],bool a[],int n) //活动安排贪心算法 {
a[0]=1;
int i;
int j=1,count=1;
for(i=1;i
{
if(s[i]>=f[j])
{
a[i]=1;
j=i;
count++;
}
else a[i]=0;
}
return count;
}
void main()
{
int i,n;
int p;
int s[100],f[100];
bool a[100];
printf("输入节目数：\n");
scanf("%d",&n);
printf("请依次输入节目的开始和结束时间\n"); for(i=0;i
{
scanf("%d %d",&s[i],&f[i]);
}
sort(s,f,n);
p=activemanage(s,f,a,n);
printf("安排的节目个数为:%d\n",p);
printf("节目的选取情况为(0表示不选 1表示选取):\n"); for(i=0;i
printf("%d ",a[i]);
printf("\n");
}