问题描述：假设要用很多个教室对一组活动进行调度。我们希望使用尽可能少的教室来调度所有活动。请给出一个算法，来确定哪一个活动使用哪一间教室。这个问题也被称为区间图着色问题，即相容的活动着同色，不相容的着不同颜色，使得所用颜色数最少。
解法思想：
其实我们知道，对于单个教室我们可以用贪心算法进行求解，但是对于这个区间图的问题，我们采用的方法是多次的贪心。其实你想想看，你无非就是要使那些活动
全部被安排完吧，当然这样安排的方法很多，如何使得安排后的教室最小呢？？？？
这明显也是个贪心的问题。聪明的人很快地想到，是不是可以多次的贪心呢？也就是说我对这些活动作一个标记，开始全部标记为”未安排“，第一次的时候就采用贪心算
法尽可能地用一间教室安排尽可能多的活动进去，然后将安排过的活动标记为”己安排“。然后对剩下的活动再进行用同样的贪心算法进行安排。
源代码
#ifndef INTERVAL_GRAPH_COLORING_H#define INTERVAL_GRAPH_COLORING_Hstruct Activity{ int startTime; int endTime; bool isArranged; //标记是否己被安排过}; int greedyCore(Activity *activityArr,int Length); int intervalGraphColoringRoomNumber(int *startTime,int *endTime,int Length){ Activity *activityArr=new Activity[Length-1]; for(int i=0;i<Length; i++){//初使化活动 activityArr[i].startTime=startTime[i]; activityArr[i].endTime=endTime[i]; activityArr[i].isArranged=false; } int usedActivity=0; //己安排过的活动 int roomArrangedCount=0; //教室的计数 while(usedActivity<Length-1){//不停地贪心选择活动，直到所有的活动己安排完。 usedActivity+=greedyCore(activityArr,Length); roomArrangedCount++; } return roomArrangedCount; }//贪心算法的核心，返回本次贪心算法所安排的活动数。int greedyCore(Activity *activityArr,int Length){ int firstunusedActivity=0; for(int i=0;i<Length-1; i++){ if(!activityArr[i].isArranged){ firstunusedActivity=i; break; } } int lastArrangedActivity=firstunusedActivity; int arrangedActiveityCount=1; for(int i=firstunusedActivity+1;i<Length;i++){ if(!activityArr[i].isArranged){ if(activityArr[i].startTime>=activityArr[lastArrangedActivity].endTime){ activityArr[i].isArranged=true; arrangedActiveityCount++; lastArrangedActivity=i; } } } return arrangedActiveityCount; }#endif 测试代码 #include"intervalGraphColoring.h"int main(){ 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}; std::cout<<intervalGraphColoringRoomNumber(start_time,end_time,11); } 来自为知笔记(Wiz)转载于:https://www.cnblogs.com/yml435/p/4660196.html
相关资源：采用贪心法求解着色问题（JAVA）