# 问题描述

设有 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;
}