算法导论 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; 这条语句的，当我们找到一个合适的教室时候，没有这段语句后，还是要进行循环，在后面的教室中再找一个合适的教室中，如果没有找到，就再新建一个。。于是教室的数目就是你的活动数目。