教室课程调度问题的两种解法（区间着色问题）

#include "h1.h" void timeQuickSort(Class c[], int n, int flag){ //快排，当flag==1时，按finishTime排序；当flag==0时，按 //startTime排序 qSort(c, 1, n, flag); } void qSort(Class c[], int low, int high, int flag){ if(low < high){ int pivotKey = partition(c, low, high, flag); qSort(c, low, pivotKey-1, flag); qSort(c, pivotKey+1, high, flag); } } int partition(Class c[], int low, int high, int flag){ Class pivot = c[low]; while(low < high){ if(flag == 1){ while(low<high && c[high].finishTime>=pivot.finishTime){ high--; } } else{ while(low<high && c[high].startTime>=pivot.startTime){ high--; } } c[low] = c[high]; if(flag == 1){ while(low<high && c[low].finishTime<=pivot.finishTime){ low++; } } else{ while(low<high && c[low].startTime<=pivot.startTime){ low++; } } c[high] = c[low]; } c[low] = pivot; return low; } void classroomDistributionGreedy(Class c[], int n, int classroom[][MAXSIZE]){ int i, j, k, flag; //i denotes the i'th classroom, j denotes the j'th class. flag = 1; //A flag to check whether a new classroom is needed. k = 1; //The k'th class of a very classroom, initial value is 1. for(i=1; i<=n; i++){ k=1; if( flag ){ flag = 0; for(j=1; j<=n; j++){ if( !c[j].flag && classroom[i][1]==0 ){ //Find the first class of a new classroom. classroom[i][k] = j; c[j].flag = 1; //The j'th class is distributed. k++; flag = 1; } else if(!c[j].flag && (c[classroom[i][k-1]].finishTime<=c[j].startTime)){ classroom[i][k] = j; c[j].flag = 1; k++; flag = 1; } } } else{ break; } } } void printCourseDistributed(int classroom[][MAXSIZE]){ int i, j, flag; flag = 1; for(i=1; i<=6; i++){ if( flag ){ flag = 0; printf("The courses of the %d 'th classroom:\n", i); for(j=1; j<=6; j++){ if(classroom[i][j] == 0){ break; } else{ printf("%d ", classroom[i][j]); flag = 1; } } printf("\n"); } else{ break; } } } void classroomDistribution(Class c[], int n, int classroom[][MAXSIZE]){ int i, k; //i denotes the i'th course. k denotes the k's classroom. int position[MAXSIZE] = {0}; //The flag to record the last course's position added to each classroom. for(i=1; i<=n; i++){ k = 1; while(c[classroom[k][position[k]]].finishTime>c[i].startTime){ k++; } flag[k]++; classroom[k][position[k]] = i; } } int main(){ int i; Class c[7]; int classroom[MAXSIZE][MAXSIZE] = {0}; for(i=0; i<=6; i++){ c[i].flag = 0; } c[6].startTime=1; c[6].finishTime=3; c[5].startTime=2; c[5].finishTime=4; c[4].startTime=3; c[4].finishTime=5; c[3].startTime=4; c[3].finishTime=6; c[2].startTime=5; c[2].finishTime=7; c[1].startTime=6; c[1].finishTime=8; c[0].startTime=0; c[0].finishTime=0;//Initiate class values. //timeQuickSort(c, 6, 0); //Sort according to starting time of each course. //classroomDistribution(c, 6, classroom);//Direct strategy. timeQuickSort(c, 6, 1);//Sort according to finishing time of each course. classroomDistributionGreedy(c, 6, classroom);//Greedy strategy printCourseDistributed(classroom); return 0; }