贪心算法之任务选择问题

一、理论推导思路

问题描述：给定n个活动的集合S = {a₁, a₂, ..., aₙ}，每个活动有开始时间start[i]和结束时间end[i]。要求选择最多的互不重叠的活动。

贪心策略：
每次选择结束时间最早的活动，这样可以为后续活动留下更多时间。具体步骤如下：

1. 将所有活动按结束时间升序排序。
2. 初始化一个空集合selected，并选择第一个活动（结束时间最早）。
3. 遍历后续活动，若当前活动的开始时间不早于最后一个选中活动的结束时间，则选中该活动。

二、算法正确性证明

证明方法：交换论证（Exchange Argument）。

假设：存在一个最优解A，其第一个活动的结束时间晚于贪心解的第一个活动的结束时间

步骤：

1. 设A的第一个活动为，其结束时间end[k] ≥ end[1]。
2. 若将替换为，则新的解 A'的活动数量至少与 A相同（因为的结束时间更早，后续可选活动更多）。
3. 因此，贪心解是最优解的一部分。
4. 递归地，剩下的子问题同样满足贪心选择性质，最终得到全局最优解。

三、算法步骤

1. 输入处理：将活动存储为列表(start, end)。
2. 排序：按活动的end升序排序。
3. 初始化：选择第一个活动（end最小），记录其结束时间last_end。
4. 遍历选择：从第二个活动开始，若当前活动的start ≥ last_end，则选中该活动，并更新last_end。
5. 输出结果：选中的活动集合。

四、时间复杂度计算

1. 排序：O(n log n)（基于比较的排序）。
2. 遍历选择：O(n)（线性扫描）。
3. 总时间复杂度：O(n log n)。

五、实例分析

示例输入：
活动列表如下（按原顺序）：

活动1: start=1, end=3  
活动2: start=2, end=5  
活动3: start=4, end=7  
活动4: start=6, end=8  
活动5: start=5, end=9  
活动6: start=8, end=10  

步骤解析：

1. 排序后：按end升序排列为活动 1、活动 2、活动 3、活动 4、活动 5、活动 6。
2. 选择过程：
   • 选活动 1（end=3）。
   • 活动 2 的 start=2 < 3 → 跳过。
   • 活动 3 的 start=4 ≥ 3 → 选活动 3（end=7）。
   • 活动 4 的 start=6 < 7 → 跳过。
   • 活动 5 的 start=5 < 7 → 跳过。
   • 活动 6 的 start=8 ≥ 7 → 选活动 6（end=10）。
3. 结果：选中活动 1、3、6，共 3 个活动。

六、代码示例（Python）

def activity_selection(activities):
    # 按结束时间升序排序
    sorted_activities = sorted(activities, key=lambda x: x[1])
    selected = []
    last_end = -1
    for start, end in sorted_activities:
        if start >= last_end:
            selected.append((start, end))
            last_end = end
    return selected

# 示例输入
activities = [
    (1, 3), (2, 5), (4, 7), (6, 8), (5, 9), (8, 10)
]
selected = activity_selection(activities)
print("选中的活动：", selected)

输出：

选中的活动： [(1, 3), (4, 7), (8, 10)]

七、算法总结

• 贪心策略的有效性：活动选择问题满足贪心选择性质和最优子结构，因此贪心算法能得到全局最优解。
• 关键步骤：排序和线性扫描，时间复杂度为O(n log n)。
• 应用场景：类似的调度问题（如任务调度、资源分配）可尝试贪心策略，但需验证贪心选择性质。