贪心算法--活动安排问题
Greedy algorithm----核心就是用最小的牺牲做最多的事情，这里我做了一个活动的安排问题，对于一个酒店的会议室安排会议，对于每个的公司都有自己的会议时间，酒店当然是越能够安排多的活动，它就可以越挣钱。也就是尽可能多的安排最多的活动，我们设计活动：就是前一个活动完了马上安排下一个活动，这样安排的会议就可以减少冲突还有会议次数要尽可能的多，而且会议不冲突。
会议制定一般是：开始时间，结束时间。我们应该考虑的是要以结束时间来考虑安排活动。其中的原因很简单，你考虑开始，会有冲突，它什么时候结束，会影响后面活动，所以我们先安结束时间排序，只要下一个活动时间大于前一个活动开始时间就可以执行该活动了。
构建活动的类型：
typedef int data;
typedef struct Active{
data start;
data end;
unsigned int on;
//活动能否进行，1表示进行，0-表示不能
}Active;
活动输入：
void IniActive(Active arr[],int size)
{
for(int i=0;i<size;i++)
arr[i].on=0;
//0表示为不能的进行活动
for(int i=0;i<size;i++){
printf("the start of active:");
scanf("%d",&arr[i].start);
printf("the end of active:");
scanf("%d",&arr[i].end);
}
}
活动按照结束时间排序：
void SortActive(Active arr[],int size)
{
int i,j;
//插入排序
for( i=0;i<size-1;i++)
{
for(j=i+1;j<size;j++)
{
if(arr[i].end>arr[j].end)
{
Active temp=arr[j];
arr[j]=arr[i];
arr[i]=temp;
}
}
}
}
活动安排算法：下一个活动结束时间大于上一个活动的开始时间
int ArrangeActive(Active arr[],int size)
{
int count=1;
arr[0].on=1;
//默认第一个可以进行
int j=0,i;
for(i=1;i<size;i++)
{
if(arr[i].start>arr[j].end)
{
arr[i].on=1;
count++;
j=i;
//纪录可以的活动
}
}
return count;
}
//输出
void printActiveIsOn(Active arr[],int size)
{
printf("the arrangement is :\n");
for(int i=0;i<size;i++)
{
if(arr[i].on==1)
{
printf("%d\t",arr[i].start);
}
}
printf("\n");
for(int i=0;i<size;i++)
{
if(arr[i].on==1)
{
printf("%d\t",arr[i].end);
}
}
printf("\n");
}
用例测试：