算法导论 16.1-4题（多个教室活动选择的问题）：
CLRS 16.1-3 假设要用很多个教室对一组活动进行调度。我们希望使用尽可能少的教室来调度所有的活动。请给出一个有效的贪心算法，来确定哪一个活动应使用哪一个教室。
来源： <
算法导论16.1-3 区间图着色(interval-graph coloring)问题(贪心算法)
>
http://blog.csdn.net/heyongluoyao8/article/details/6934198
（区间图着色贪心算法C++实现）
解决方法一：
1.对于所有活动的时间点按升序进行排序（n个活动，就有2n个时间点），记录每个时间是起始的还是终止的，在排序的时候，对于值相同的时间点，如果是终止时间点的话，就排在前面。
2.最开始，选择第一个起始时间点，把它对应的活动放入一个教室，同时记录这个起始时间点对应的终止时间点。
3.接着按序选择第i个起始时间点（只选择起始时间点），对于第i个起始时间点，比较它和已有教室中的活动的终止时间点，若大于某个终止时间点，则直接将第i个起始时间点对应的活动放进相应的教室，否则新开辟一个教室来放入这个活动。
struct Active{ int start_time; //活动的起始时间 int end_time; //活动的结束时间 int flag; //是否己被选择 int room_num;//被分配到的房间号}; /*区间图着色问题（多个教室的活动选择问题）*/int active_select_room(struct Active *act,int act_num){ for(int i=0;i<act_num; i++){ act[i].flag=0; act[i].room_num=0; } int sumRoom=1; //目前使用的教室数目 int *roomTime=new int[act_num]; //每个教室目前的最晚结束时间 roomTime[sumRoom]=act[0].end_time; //将教室0结束时间初使化为第一个活动的结束时间 act[0].flag=1; act[0].room_num=1; for(int i=1;i<act_num; i++){ //对所有活动进行循环，安排该活动到合适的教室 int j; for(j=1;j<=sumRoom; j++){ //对所有教室的结束时间进行比较，看能否安排下这个活动 if(act[i].start_time>=roomTime[j]&&!act[i].flag){ act[i].flag=1; act[i].room_num=j; roomTime[j]=act[i].end_time; break; } } if(j>sumRoom){ sumRoom++; act[i].flag=1; act[i].room_num=sumRoom; roomTime[sumRoom]=act[i].end_time; } } for(int i=0;i<act_num; i++){ std::cout<<"active number-> "<<i<<std::endl; std::cout<<"active start_time->"<<act[i].start_time<<std::endl; std::cout<<"active end_time->"<<act[i].end_time<<std::endl; std::cout<<"active room_num->" <<act[i].room_num<<std::endl; std::cout<<std::endl; } return sumRoom; }
实验数据int start_time[11]={1,3,0,5,3,5,6,8,8,2,12}; int end_time[11]={4,5,6,7,9,9,10,11,12,14,16};
如上面代码所示，我们使用最小结束时间排序，然后对每个活动的开始时间进行判断，当当前的活动的开始时间
大于某一个教室的结束时间（教室的结束时间为该教室里最晚的活动的结束时间）。如果找不到这么一个合适的
数据，则新建一个教室，将当前教室的结束时间为当前活动的结束是间，然后这个活动的flag(表示当前活动是否
己被安排了)。
教训：
在该程序中，以前写的版本，是这样的（错误段）
..................for(j=1;j<=sumRoom; j++){ // if(act[i].start_time>=roomTime[j]&&!act[i].flag){ act[i].flag=1; act[i].room_num=j; roomTime[j]=act[i].end_time; }}.....................
上面的代码相对于正确的代码而言，是少有break; 这条语句的，当我们找到一个合适的教室时候，没有这段语
句后，还是要进行循环，在后面的教室中再找一个合适的教室中，如果没有找到，就再新建一个。。于是教室
的数目就是你的活动数目。
来自为知笔记(Wiz)
转载于:https://www.cnblogs.com/yml435/p/4655581.html
相关资源：采用C++实现区间图着色问题（贪心算法）实例详解
