河海大学 · 2026秋季 · 计算思维导论
作业题1：活动安排与算法选择
先用贪心算法安排尽可能多的活动，再改变目标，用穷举法寻找总价值最大的方案。通过两道题，体会算法的选择为什么取决于问题的目标。
授课教师：谢在鹏（河海大学计算机系） · 使用C或Python完成
活动安排是在解决什么问题？
假设你负责管理一间活动室。同一天，多个社团提交了预约申请，每场活动都有固定的开始和结束时间。因为只有一个场地，同一时刻只能举行一场活动，你需要从申请中选出一部分，安排成一天的日程。
怎样判断两场活动是否冲突？例如，A活动在09:00至11:00举行，B活动在10:00至12:00举行，两者有一段时间重叠，因此不能同时选。若C活动在11:00开始，就可以紧接着A举行。本作业约定不计布置时间，结束与开始时刻相等也可以衔接。
“安排得下”和“安排得最好”有什么区别？选出的活动互不冲突，就得到一个可行方案。但可行方案往往不止一个，还需要按照目标比较它们。第一问比较活动数量，第二问比较总价值；活动数量最多的方案，不一定总价值最高。
两种算法思路怎样用在这里？贪心法每一步按一个明确规则选择活动，例如优先考虑结束早的活动，为后面腾出时间。穷举法则检查各种“选或不选”的组合，排除冲突方案，再从可行方案中选出最好的。本作业让你先实现第一种思路，再在目标改变后检验原规则，并用第二种思路求解小规模实例。
从数据到程序：每场活动需要保存编号、开始和结束时间，第二问再增加价值。程序要根据这些数据判断时间是否冲突、记录所选活动，并累计活动数量或总价值。
第一问：怎样安排更多活动？
学校只有一间活动室，有n场活动申请使用。每场活动的开始、结束时间已经确定，不能调整，也不能拆分。
目标：选择时间互不冲突的活动，使举行的活动数量最多。
问题约定
- 前一场结束时刻等于后一场开始时刻，两场可以接着举行。
- 不考虑布置和清场时间，每场活动最多选择一次。
- 输入中的活动不一定按时间排序，活动编号互不重复。
- 若有多个最优方案，输出任意一个即可。
输入与输出
第一行是活动数量n，1 ≤ n ≤ 1000。接下来n行，每行包含：
活动编号 开始时间 结束时间活动编号是不含空格的字符串。时间用当天从零点开始经过的分钟数表示，例如09:00为540。保证0 ≤ 开始时间 < 结束时间 ≤ 1440。
输出两行：第一行是最多能安排的活动数量，第二行是所选活动编号，按举行时间先后排列，用空格分隔。
示例输入
6
A 540 660
B 600 780
C 660 720
D 720 900
E 780 1020
F 900 960一种正确输出
4
A C D FA结束时C可以开始，C结束后可以安排D，再安排F。
你需要完成什么？
- 先用自然语言说明选择规则，再使用贪心算法编写程序。
- 输出最多能安排的活动数量，以及一个对应的活动安排。
- 自行设计至少三组测试，覆盖“全部冲突”“全部兼容”和“结束时刻相同”等情况。
- 用一两句话说明：为什么优先选择结束早的活动，有利于安排更多后续活动？
关注的知识：排序、贪心选择、条件判断，以及用变量保存当前安排进度。只得到一个可行安排还不够，还需要解释为什么所用规则能保证活动数量最多。
第二问：目标变为“总价值最大”
现在每场活动还有一个价值分数，表示该活动带来的综合收益。活动室、时间冲突等约束保持不变。
新目标：选择时间互不冲突的活动，使价值分数之和最大。
本题使用穷举法。为控制计算规模，规定1 ≤ n ≤ 15，每场活动的价值为1至1000的整数。其余输入约定与第一问相同。
输入与输出
第一行是活动数量n，接下来n行，每行包含：
活动编号 开始时间 结束时间 价值输出两行：第一行是最大总价值，第二行是所选活动编号，按举行时间先后排列，用空格分隔。若有多个最优方案，输出任意一个即可。
示例输入
3
A 540 660 2
B 660 780 2
C 540 780 10正确输出
10
C选择A、B可以举行两场，但总价值只有4；只选择C，总价值为10。
你需要完成什么？
- 先沿用第一问“结束最早优先”的选择规则，算出它在本例中得到的总价值，并在说明文档中记录结果。
- 判断该规则是否仍能保证价值最大，结合本例说明理由。
- 使用穷举法检查活动组合，排除时间冲突的组合，找出总价值最大的方案。不要求使用动态规划。
- 自行设计至少三组测试，检查价值相同、单场高价值活动与多场低价值活动等情况。
算法提示：一个组合由“每场活动选或不选”决定。对每个候选组合，先判断活动能否同时安排，再比较总价值。你可以自行选择组合的表示和枚举方式。
最后想一想
为什么第一问允许处理1000场活动，第二问却只要求处理最多15场？请结合自己的程序，说明需要检查的候选数量会怎样增加。