贪心算法解决会场安排问题
贪心算法解决会场安排问题。
【问题描述】
假设要在足够多的会场里安排一批活动,并希望使用尽可能少的会场。(这个问题实际上是著名的图着色问题。若将每一个活动作为图的一个顶点,不相容活动间用边相连。使相邻顶点有不同颜色的最小着色数,相应于要找的最小会场数。)
【数据输入】
由文件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<n;i++) { fscanf(fp,"%d%d",&s_t[i],&e_t[i]); } for(i=0;i<n;i++) { printf("%3d",s_t[i]); } cout<<endl; for(i=0;i<n;i++) { printf("%3d",e_t[i]); } cout<<endl; int star =1000,end=0; int s_key,e_key; for(i=0;i<n;i++) { if(s_t[i]<=star) { s_key = i; star = s_t[i]; } if(e_t[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<n;i++) { int kk = s_t[i]; if(i==s_key) { continue; } for(int j=0;j<count;j++) { if(t_c[j].ed<kk) { t_c[j].ed = e_t[i]; break; } else { t_c[count].ed = e_t[i]; count++; break; } } } printf("%3d\n",count); return 0; }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。