贪心算法解决会场安排问题

贪心算法解决会场安排问题。

【问题描述】

假设要在足够多的会场里安排一批活动，并希望使用尽可能少的会场。（这个问题实际上是著名的图着色问题。若将每一个活动作为图的一个顶点，不相容活动间用边相连。使相邻顶点有不同颜色的最小着色数，相应于要找的最小会场数。）

【数据输入】

由文件input.txt给出输入数据，第一行又一个正整数K，表示有K个待安排的活动。

接下来有K行数据，每行有两个正整数，分别表示K个待安排的活动的开始时间和结束时间。

【结束输出】

输出最少会场数。

input.txt       output.txt

5                   3

1 23

12 28

25 35

27 80

36 50

思路：遍历所有的活动时间，如果时间可叠加到前面已有活动的会场的，则叠加到已有活动；如不可叠加，则新加会场。

代码：

#include"iostream"
#include"string"
using namespace std;


struct tt
{
	int st;
	int ed;
};


int main()
{
    int n=0;
	FILE *fp;
	int num=1;
	if((fp=fopen("input.txt","r"))==NULL)
	{
        printf("Can't find the input.txt\n");
	}
	fscanf(fp,"%d",&n);

	int *s_t;
	int *e_t;
    s_t = (int *)malloc(sizeof(int)*n+1);
	e_t = (int *)malloc(sizeof(int)*n+1);
    tt *t_c;
	t_c =(tt *)malloc(sizeof(tt)*n+1);

	int i=0;
	for(i=0;i=end)
		{
			e_key = i;
			end = e_t[i];
		}
	}


	int count=0;
	t_c[0].ed = e_t[s_key];
	count ++;

	for(i=0;i