活动安排--贪心算法C语言实现

一.前言

大三下的算法设计分析课程。每周必备二道算法题。头疼。自己写的，大家看看就行。题目，我就截图 ，懒得赋文字了。

二.内容

代码：

#include<stdio.h>typedef struct{int s;//开始时间int f;//结束时间int flag;//标志位，0表示未被选择，1表示被选择} Activity;int main(){//求解活动安排的最多活动数Activity a[1000];//一天的活动int n;//现存的活动int i;//循环变量int j;//循环变量int k;int af;//活动结束时间int count;//可以安排的活动数Activity temp;scanf("%d",&n);for(i=0;i<n;i++){//说明现存要安排的活动scanf("%d%d",&a[i].s,&a[i].f);}for(i=0;i<n-1;i++){//按活动结束时间排序,选择法,从小到大排序k=i;for(j=i+1;j<n;j++){if(a[j].f<a[k].f){k=j;}}if(k!=i){temp=a[k];a[k]=a[i];a[i]=temp;}}//将活动结束时间最早的安排上a[0].flag=1;count=1;af=a[0].f;//采用贪心算法for(i=1;i<n;i++){if(a[i].s>=af){a[i].flag=1;count++;af=a[i].f;}else{a[i].flag=0;}}printf("%d",count);//输出可以安排的活动数printf("\n");return 0;}