题目描述

学校社团文化节即将举办，共有 n 个不同的活动供同学们参加。每个活动都有明确的开始时间和结束时间。 小明想参加尽可能多的活动，但他不能同时参加两个时间重叠的活动。如果一个活动的结束时间等于另一个活动的开始时间，那么这两个活动是可以连续参加的。 请你帮小明计算：他最多能参加多少个活动？并按时间顺序输出他应该选择的活动编号。

输入格式

第一行输入一个正整数 n（1 ≤ n ≤ 1000），表示活动的总数量。 接下来 n 行，每行输入两个整数 s_i 和 e_i（0 ≤ s_i < e_i ≤ 10000），分别表示第 i 个活动的开始时间和结束时间。活动编号从 1 到 n 依次排列。

输出格式

第一行输出一个整数 k，表示小明最多能参加的活动数量。 第二行输出 k 个整数，按时间顺序表示小明选择的活动编号。如果存在多个最优解，输出任意一个即可。

6
1 3
2 4
3 5
4 6
5 7
6 8

3
1 3 5

样例 1 解释 最优选择方案有多种，例如： 方案 1：活动 1（1-3）→ 活动 3（3-5）→ 活动 5（5-7） 方案 2：活动 2（2-4）→ 活动 4（4-6）→ 活动 6（6-8） 两种方案都能参加 3 个活动，这是最多的数量。

6
1 2
3 4
0 6
5 7
8 9
1 5

4
1 2 4 5

样例 2 解释 按结束时间从小到大排序后，活动顺序为：1（1-2）、2（3-4）、6（1-5）、3（0-6）、4（5-7）、5（8-9） 贪心选择策略：每次选当前结束最早且不与已选活动重叠的活动。 选活动 1（结束时间 2） 选活动 2（开始时间 3 ≥ 2，结束时间 4） 选活动 4（开始时间 5 ≥ 4，结束时间 7） 选活动 5（开始时间 8 ≥ 7，结束时间 9） 最终共参加 4 个活动，这是全局最优解。

题目要求

必须使用贪心算法解决本题
核心策略：将所有活动按结束时间从小到大排序
活动不重叠判定：后一个活动的开始时间 ≥ 前一个活动的结束时间
数据范围保证所有输入都是合法的正整数

【贪心算法经典应用】活动选择详解

活动选择问题是算法研究中的一个经典问题，广泛应用于资源分配领域，如会议室预订、课程安排等场景。问题的核心是在给定一组活动，每个活动都有一个开始时间和一个结束时间，要求选择最大数量的互不重叠的活动。 问题定义

给定( n )个活动,
每个活动( i )都有一个开始时间 ( s_i )和结束时间 ( e_i )。
选择一组最大的互不相交的活动集合,
即在任意选定的两个活动( i )和( j )，
满足( i =！j )，则( e_i <= s_j )或( e_j <= s_i )。

贪心选择策略

活动选择问题的贪心策略是基于活动的结束时间进行选择，即总是选择结束时间最早的活动。按照这种策略进行选择的理由如下：
• 选择结束最早的活动将留给剩余活动最大的时间空间，从而增加后续选择活动的可能性。
• 这种策略确保了每次选择都是局部最优的，即在当前剩余的活动集合中，选择一个与已选择的活动都不重叠且结束最早的活动。

算法步骤

1. 输入：活动时间对列表 ((s_1, e_1), (s_2, e_2), …, (s_n, e_n))。
2. 排序：按照活动的结束时间( e_i )进行升序排序。
3. 初始化：选择排序后的第一个活动，因为它的结束时间最早。
4. 迭代选择：
• 从剩余的活动中选择一个与已选择集合中所有活动都不重叠的活动，具体为选择结束时间最早且开始时间不早于最后一个已选择活动的结束时间的活动。
5. 输出：返回选择的活动集合。

算法分析

• 时间复杂度：排序活动的时间复杂度为 ( O(n log n) )，选择活动的时间复杂度为 ( O(n) )，因此总时间复杂度为 ( O(n log n) )。
• 空间复杂度：算法的空间复杂度为 ( O(1) )，如果不考虑输入数据的存储，只需常数空间用于索引和临时变量。
为了更清晰地理解活动选择问题及其贪心算法实现，我们可以通过图解的方式来逐步展示算法的工作原理。图解将帮助我们可视化贪心选择策略是如何在实践中被应用以解决问题的。

活动选择问题的图解 以下一组活动，每个活动都有一个开始时间和结束时间：

步骤 1: 活动按结束时间排序 步骤 2: 选择活动

接下来，我们选择结束时间最早的活动，并排除所有与其重叠的活动：
1. 选择活动 1 (结束时间 4) - 选择这个活动因为它是第一个结束的。
2. 排除活动 2 (因为它在活动 1 还未结束时开始了，即与活动 1 重叠)。
3. 排除活动 3 (同样重叠于活动 1)。
4. 选择活动 4 (下一个未重叠活动，开始时间 5，结束时间 7)。
5. 排除活动 6 (与活动 4 重叠)。
6. 选择活动 5 (下一个未重叠活动，开始时间 8，结束时间 9)。

图解表示 以下是活动时间线的图示，显示了如何选择活动：

时间线: 0---------1---------2---------3---------4---------5---------6---------7---------8---------9
活动 1:          [-----------------------------]
活动 2:                               [--------------------]
活动 3: [-----------------------------------------------------------]
活动 4:                                                   [-------------------]
活动 5:                                                                                 [----------]
活动 6:                                                   [----------------------------------------]

选择的活动: 1, 4, 5 步骤 3: 最终结果

我们最终选择的活动集合为活动 1, 4, 5，
这是根据贪心算法从排序后的活动列表中选择的最大互不相交集。

结论

活动选择问题的贪心算法非常高效且易于实现。通过基于结束时间的排序和选择，它可以找到最大的互不相交的活动集合，适用于许多实际的调度和资源分配问题。此外，该问题的解法也深刻地体现了贪心算法设计的美妙和实用性，即通过每步的局部最优选择达到全局最优解