贪心算法活动安排问题（贪心算法活动安排问题C语言）

## 贪心算法活动安排问题

简介

活动安排问题是典型的应用贪心算法的场景。它描述的是如何在有限的时间范围内，选择尽可能多的、互不冲突的活动进行。例如，一个会议室在一天内有多个活动申请使用，每个活动都有其开始时间和结束时间，目标是安排尽可能多的活动。贪心算法提供了一种高效的解决方案，其核心思想是每次选择结束时间最早的活动，从而为后续活动留下更多的时间。

1. 问题描述

假设有n个活动申请使用同一个资源（例如会议室、教室等），每个活动i都有一个开始时间s[i]和结束时间f[i]，其中0 ≤ s[i] < f[i]。如果两个活动i和j的时间区间不重叠，即f[i] ≤ s[j] 或 f[j] ≤ s[i]，则称它们是兼容的。目标是在这n个活动中选择一个最大的兼容活动子集。

2. 贪心策略

解决活动安排问题的贪心策略是：总是选择结束时间最早的活动。 这个策略的直觉是，尽早结束当前活动可以为后续活动留下更多的时间。

3. 算法步骤

1.

排序:

将所有活动按照结束时间f[i]非递减排序。如果结束时间相同，则可以按照开始时间非递减排序（这对于算法的正确性没有影响，但可能影响最终选择的具体活动）。 2.

初始化:

选择第一个活动（即结束时间最早的活动），并将其加入结果集合A。 3.

迭代:

对于剩余的活动，依次判断其开始时间是否晚于当前已选择活动的结束时间。如果是，则选择该活动并将其加入结果集合A，并更新当前已选择活动的结束时间。 4.

结束:

当遍历完所有活动后，结果集合A即为所求的最大兼容活动子集。

4. 伪代码

``` Activity_Selection(activities):// activities: 包含所有活动的数组，每个活动是一个包含开始时间和结束时间的对象// activities 已经按照结束时间非递减排序A = {activities[0]} // 选择第一个活动last_finish_time = activities[0].finishfor i = 1 to activities.length - 1:if activities[i].start >= last_finish_time:A.add(activities[i])last_finish_time = activities[i].finishreturn A ```

5. 正确性证明 (简略)

可以使用交换论证法证明贪心策略的正确性。假设存在一个最优解不包含最早结束的活动a1，而包含另一个与a1冲突的活动ak。由于a1结束时间最早，f[a1] <= f[ak]，将ak替换为a1，得到的仍然是一个可行解，且活动数量不变。因此，总是选择最早结束的活动不会导致最优解的丢失。

6. 时间复杂度分析

算法的主要时间消耗在排序步骤，其时间复杂度为O(nlogn)，其中n是活动的个数。后续的迭代选择步骤的时间复杂度为O(n)。因此，整个算法的时间复杂度为O(nlogn)。

7. 示例

假设有如下活动及其开始时间和结束时间：| 活动 | 开始时间 | 结束时间 | |---|---|---| | 1 | 0 | 6 | | 2 | 3 | 5 | | 3 | 1 | 4 | | 4 | 5 | 7 | | 5 | 3 | 8 | | 6 | 5 | 9 | | 7 | 6 | 10 | | 8 | 8 | 11 | | 9 | 8 | 12 | | 10 | 2 | 13 | | 11 | 12 | 14 |按照结束时间排序后，应用贪心算法，可以选择的活动依次为：活动3，活动4，活动8，活动11。

8. 总结

贪心算法提供了一种高效且易于实现的解决活动安排问题的方法。通过每次选择结束时间最早的活动，可以保证选择尽可能多的兼容活动。 需要注意的是，贪心算法并非对所有问题都能得到最优解，但在活动安排问题中，贪心策略可以保证找到全局最优解。

贪心算法活动安排问题**简介**活动安排问题是典型的应用贪心算法的场景。它描述的是如何在有限的时间范围内，选择尽可能多的、互不冲突的活动进行。例如，一个会议室在一天内有多个活动申请使用，每个活动都有其开始时间和结束时间，目标是安排尽可能多的活动。贪心算法提供了一种高效的解决方案，其核心思想是每次选择结束时间最早的活动，从而为后续活动留下更多的时间。**1. 问题描述**假设有n个活动申请使用同一个资源（例如会议室、教室等），每个活动i都有一个开始时间s[i]和结束时间f[i]，其中0 ≤ s[i] < f[i]。如果两个活动i和j的时间区间不重叠，即f[i] ≤ s[j] 或 f[j] ≤ s[i]，则称它们是兼容的。目标是在这n个活动中选择一个最大的兼容活动子集。**2. 贪心策略**解决活动安排问题的贪心策略是：总是选择结束时间最早的活动。 这个策略的直觉是，尽早结束当前活动可以为后续活动留下更多的时间。**3. 算法步骤**1. **排序:** 将所有活动按照结束时间f[i]非递减排序。如果结束时间相同，则可以按照开始时间非递减排序（这对于算法的正确性没有影响，但可能影响最终选择的具体活动）。 2. **初始化:** 选择第一个活动（即结束时间最早的活动），并将其加入结果集合A。 3. **迭代:** 对于剩余的活动，依次判断其开始时间是否晚于当前已选择活动的结束时间。如果是，则选择该活动并将其加入结果集合A，并更新当前已选择活动的结束时间。 4. **结束:** 当遍历完所有活动后，结果集合A即为所求的最大兼容活动子集。**4. 伪代码**``` Activity_Selection(activities):// activities: 包含所有活动的数组，每个活动是一个包含开始时间和结束时间的对象// activities 已经按照结束时间非递减排序A = {activities[0]} // 选择第一个活动last_finish_time = activities[0].finishfor i = 1 to activities.length - 1:if activities[i].start >= last_finish_time:A.add(activities[i])last_finish_time = activities[i].finishreturn A ```**5. 正确性证明 (简略)**可以使用交换论证法证明贪心策略的正确性。假设存在一个最优解不包含最早结束的活动a1，而包含另一个与a1冲突的活动ak。由于a1结束时间最早，f[a1] <= f[ak]，将ak替换为a1，得到的仍然是一个可行解，且活动数量不变。因此，总是选择最早结束的活动不会导致最优解的丢失。**6. 时间复杂度分析**算法的主要时间消耗在排序步骤，其时间复杂度为O(nlogn)，其中n是活动的个数。后续的迭代选择步骤的时间复杂度为O(n)。因此，整个算法的时间复杂度为O(nlogn)。**7. 示例**假设有如下活动及其开始时间和结束时间：| 活动 | 开始时间 | 结束时间 | |---|---|---| | 1 | 0 | 6 | | 2 | 3 | 5 | | 3 | 1 | 4 | | 4 | 5 | 7 | | 5 | 3 | 8 | | 6 | 5 | 9 | | 7 | 6 | 10 | | 8 | 8 | 11 | | 9 | 8 | 12 | | 10 | 2 | 13 | | 11 | 12 | 14 |按照结束时间排序后，应用贪心算法，可以选择的活动依次为：活动3，活动4，活动8，活动11。**8. 总结**贪心算法提供了一种高效且易于实现的解决活动安排问题的方法。通过每次选择结束时间最早的活动，可以保证选择尽可能多的兼容活动。 需要注意的是，贪心算法并非对所有问题都能得到最优解，但在活动安排问题中，贪心策略可以保证找到全局最优解。