# 问题描述

设有 n 个活动的集合 E = {1,2,…,n},其中每个活动都要求使用同一资源,如演讲,会议等,而在同一时间内只有一个活动能使用这一资源。

每个活动 i 都有一个要求使用该资源的起始时间 s [i] 和一个结束时间 f [i],且 s [i] <f [i]。如果选择了活动 i,则它在半开时间区间 [s [i] ,f [i]) 内占用资源。若区间 [s [i]] , f [i]) 与区间 [s [j], f [j]) 不相交,则称活动 i 与活动 j 是相容的。当 s [i]≥f [j] 或 s [j]≥f [i] 时,活动 i 与活动 j 相容。

活动安排问题就是在所给的活动集合中选出最大的相容活动子集合。

# 数据

在这里插入图片描述

# 算法策略:

活动结束早的优先选,排序使 f [1]<f [2]<f [3]<.......<f [n],从前向后挑选活动

# 代码

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
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 面向对象方法解决问题
struct Activity
{
int begin_time;// 开始时间
int end_time;// 结束时间

Activity(int b, int e) :begin_time(b), end_time(e) {}

// 重载运算符<
// 根据活动的结束时间早晚进行比较
bool operator < (Activity a)
{
return (this->end_time < a.end_time)
}
};

// 重载运算符<<
// 打印活动开始时间和结束时间
ostream& operator<<(ostream &cout_, Activity a)
{
cout_ << "活动开始时间为:" << a.begin_time << "活动结束时间为:" << a.end_time;
return cout_;
}

/*
@param act_sets 活动集合
@return 最大相容活动子集
*/
vector<int> ArrangeActivity(vector<Activity> act_sets)
{
vector<int> res_sets;
int current_time = 0;// 记录当前时间
int activity_index = 0;

while (activity_index != act_sets.size())
{
// 上一个被安排活动的结束时间小于当前活动的开始时间
if (current_time <= act_sets[activity_index].begin_time)
{
// 添加当前活动编号
res_sets.push_back(activity_index + 1);
// 记录下当前活动结束时间
current_time = act_sets[activity_index].end_time;
}
// 继续判断下一个活动是否符合安排条件
activity_index++;
}
return res_sets;
}

int main()
{
// 准备数据
vector<Activity> act_sets = { Activity(1,4),Activity(8, 12),Activity(0,6)\
, Activity(3, 5), Activity(3, 8), Activity(2, 13), Activity(5, 9)\
, Activity(8, 11), Activity(6, 10), Activity(5, 7), Activity(12, 14) };

// 根据活动的结束时间从早到晚对活动进行排序
sort(act_sets.begin(), act_sets.end());
//for (int i = 0; i < act_sets.size(); ++i)
// cout << act_sets[i] << endl;

vector<int> res = ArrangeActivity(act_sets);

cout << "最大相容活动子集为:" << endl;
for (int i = 0; i < res.size(); ++i)
cout << res[i] << " ";

return 0;
}