本文所述算法即假设要用很多个教室对一组活动进行调度。我们希望使用尽可能少的教室来调度所有活动。采用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 100
using 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;
}
|