【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 %dn",((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】--------------------------------------------------------------------------