本文所述算法即假设要用很多个教室对一组活动进行调度。我们希望使用尽可能少的教室来调度所有活动。采用C++的贪心算法,来确定哪一个活动使用哪一间教室。
对于这个问题也常被称为区间图着色问题,即相容的活动着同色,不相容的着不同颜色,使得所用颜色数最少。
具体实现代码如下:
//贪心算法 #include "stdafx.h" #include#define N 100 using namespace std; struct Activity { int number; //活动编号 int begin; //活动开始时间 int end; //活动结束时间 bool flag;//此活动是否被选择 int roomNum; //此活动在哪间教室举行 }; //对于活动集,按照结束时间递增排序,使用快速排序 void fast_sort(Activity *act,int f,int t) { if(f =time[j])&&(!act[i].flag)) { //此活动的教室号码 act[i].roomNum = j; //此活动被选择 act[i].flag = true; //更新此教室的最晚时间 time[j] = act[i].end; //被选择的活动数目加1 sumAct ++; } } //说明活动没有全部被选择,而所有活动都遍历一遍 //所以需要再加一个教室,从头再遍历 if(sumAct >cases; while(cases--) { int n; cout<<"请输入活动的数目:"< >n; int i; for(i=0;i >act[i].begin; cout<<"活动"<>act[i].end; } fast_sort(act,0,n-1); int roomNum =select_room(act,time,n); cout<<"所用教室总数为:"<