【TDTX】
【C99】
【注】相容活动:两活动之间可顺序化,即两个需要执行的时间段无重叠
如:活动A:开始点0,结束点3;活动B:开始点1,结束点6;则两活动不相容,有重叠时间段。
一、Txsf.c
#include <stdio.h>
#include <stdlib.h>
struct hd
{
int inorder;//活动输入顺序
int start;
int end;
};
int kx(const void* q,const void* p)
{
//printf("%d %d\n",((struct hd*) q)->end,((struct hd*) p)->end);
return ((struct hd*) q)->end - ((struct hd*) p)->end;
}
int main()
{
int n;
int i;
printf("输入活动个数n:");
scanf("%d",&n);
struct hd mhd[n];//C99
for(i = 0;i < n;i++)
{
printf("输入第%d个活动-开始点与结束点:",i+1);
scanf("%d %d",&(mhd[i].start),&(mhd[i].end));
mhd[i].inorder = i+1;
}
qsort(mhd,n,sizeof(mhd[0]),kx);//stdlib中的qsort()函数,给mhd[n]结构体数组排序
puts("\n依照活动的结束时间点,按非递减快速排序所有活动,得到活动顺序为:");
for(i = 0;i < n;i++)
{
printf("活动%d(开始-%d,结束-%d)\n",mhd[i].inorder,mhd[i].start,mhd[i].end);
}
int B[n];
for(i = 0;i < n;i++)
{
//将B[n]数组全部初始化为-1
B[i] = -1;
}
int tend = -1;
int k = 0;
tend = mhd[0].end;
B[0] = 0;
puts("\n按照贪心算法所得活动执行顺序集合为:\n");
puts("1.一边选择活动一边输出该元素:");
printf("\n活动%d",mhd[0].inorder);
for(i = 0;i < n;i++)
{
if( tend <= mhd[i].start )
{
B[k++] = i;//记录被选中活动在排序后mhd[n]数组中的位置
printf("-活动%d",mhd[i].inorder);
tend = mhd[i].end;
}
}
puts("\n");
puts("2.通过记录数组B[n]输出结果:");
printf("\n活动%d",mhd[0].inorder);
for(i = 0;i < n;i++)
{
if(B[i] == -1)
{
break;
}
printf("-活动%d",mhd[B[i]].inorder);
}
puts("");
system("pause");
return 0;
}
二、 运行结果示例
2.1 输入8个活动
8
3 6
1 3
5 9
0 2
7 9
9 12
9 11
12 14
2.2 输入9个活动
9
3 6
1 3
5 9
0 2
7 9
9 12
9 11
12 14
2 5
------------------------------------------------------第十一次发项目类文章有点激动啊!-----------------------------------------------------
-----------------------------------------------------【C语言—微项目—自编练习】----------------------------------------------------------
----------------------------------------------------------------【TDTX】--------------------------------------------------------------------------