本文所述算法即假设要用很多个教室对一组活动进行调度。我们希望使用尽可能少的教室来调度所有活动。采用C++的贪心算法，来确定哪一个活动使用哪一间教室。
对于这个问题也常被称为区间图着色问题，即相容的活动着同色，不相容的着不同颜色，使得所用颜色数最少。
具体实现代码如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
|
//贪心算法#include "stdafx.h"#include<iostream>#define N 100using 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<t) { int i = f-1,j = f; Activity a = act[t]; while(j<t) { if(act[j].end<=a.end) { i++; Activity temp1 = act[i]; act[i] = act[j]; act[j] = temp1; } j++; } Activity temp2 = act[t]; act[t] = act[i+1]; act[i+1] = temp2; fast_sort(act,f,i); fast_sort(act,i+2,t); }}//把每一个相容的活动集添加到一个教室，使得教室数目最少int select_room(Activity *act,int *time,int n){ int i = 1; int j = 1; int sumRoom; //目前所用的教室数目 sumRoom = 1; int sumAct; //目前有多少活动被选择了 sumAct = 1; //教室1目前最晚时间为排在最前面的活动的结束时间 time[1] = act[0].end; //最先结束的活动放在教室1中 act[0].roomNum = 1; for(i=1;i<n;i++) { for(j=1;j<=sumRoom;j++) { //如果活动act[i]的开始时间大于等于j教室目前的最晚结束时间且此活动还没有被选择， //则此活动与目前这间教室里面的活动是兼容的，可以加入进去 if((act[i].begin>=time[j])&&(!act[i].flag)) { //此活动的教室号码 act[i].roomNum = j; //此活动被选择 act[i].flag = true; //更新此教室的最晚时间 time[j] = act[i].end; //被选择的活动数目加1 sumAct ++; } } //说明活动没有全部被选择，而所有活动都遍历一遍 //所以需要再加一个教室，从头再遍历 if(sumAct<n&&i==n-1) { //从头开始遍历 i = 0; //教室数目加1 sumRoom = sumRoom+1; } } return sumRoom;}int _tmain(int argc, _TCHAR* argv[]){ int cases; Activity act[N]; //用来记录每个教室目前最晚完成的活动的结束时间 int time[N]; cout<<"请输入案例的个数："<<endl; cin>>cases; while(cases--) { int n; cout<<"请输入活动的数目："<<endl; cin>>n; int i; for(i=0;i<n;i++) { time[i+1] = 0; //初始化每个教室目前最晚的时间为0 act[i].number = i+1; act[i].flag = false; //初始化每个活动都未被选择 act[i].roomNum = 0; //初始化每个活动都占用教室 cout<<"活动"<<i+1<<"开始时间："; cin>>act[i].begin; cout<<"活动"<<i+1<<"结束时间："; cin>>act[i].end; } fast_sort(act,0,n-1); int roomNum =select_room(act,time,n); cout<<"所用教室总数为："<<roomNum<<endl; cout<<"每个活动在哪一个教室中："<<endl; for(i=0;i<n;i++) { cout<<"活动"<<act[i].number<<"在教室"<<act[i].roomNum<<"中"<<endl; } } system("pause"); return 0;} |
