C++_测试和训练活动安排问题

问题描述、

问题描述：存在一组由n个活动构成的集合S = {a1, ..., an}

1. 这些活动共享同一个资源，而该资源在同一时间只能被一个活动使用

2. 每个活动都具有特定的开始时间si和结束时间fi；若该活动被选中，则任务ai将在半开区间[si, fi)内执行

3. 若两个活动ai和aj的时间段没有重叠，则称这两个活动为兼容

目标是选择一个兼容性最高的活动集合，使其包含的活动数量达到最大值

设计思路

设计思路：采用回溯算法进行求解，利用数组s[N]存储各个事件的起始与终止时刻，m[N]用于记录当前获取的最大兼容活动集合，v[N]则保存当前最大兼容集合对应的起始与终止时间。Vmax表示当前最大兼容集合所包含的事件数量。若某一事件可以加入栈（即与栈中已存在的元素不存在时间冲突），则将其压入栈中；若无法继续压入新事件，则比较此时栈中的总事件数与Vmax，若前者更大，则更新Vmax以及v[N]和m[N]。当i>n时需进行退栈操作；如果此时栈为空，则程序结束，并输出最终得到的Vmax、v[N]及m[N]。

数据结构：

s[N]用于存储各个事件的起始及终止时刻，

m[N]用于记录当前获得的最大兼容活动集合，

v[N]用于保存当前最大兼容集合对应的起始及终止时刻

a[N]作为工作数组，用来存放当前栈内的所有活动，

V