贪心算法实战：用Python解决活动选择问题

1. 贪心算法核心思想与应用场景

贪心算法（Greedy Algorithm）是一种在每一步选择中都采取当前状态下最优决策的算法策略。它通过局部最优选择的累积来构建全局解，这种"短视"的策略虽然不能保证对所有问题都获得全局最优解，但在许多实际场景中表现出极高的效率。

贪心算法的两个关键性质：

• 贪心选择性质：每一步的局部最优选择能导向全局最优解
• 最优子结构：问题的最优解包含其子问题的最优解

# 贪心算法通用伪代码框架
def greedy_algorithm(problem):
    solution = []
    while not is_solution_complete(solution):
        candidate = select_best_candidate(problem)
        if is_feasible(candidate, solution):
            solution.append(candidate)
    return solution

贪心算法特别适合解决以下类型的问题：

• 活动选择/区间调度问题
• 霍夫曼编码（数据压缩）
• 最小生成树（Prim/Kruskal算法）
• 最短路径问题（Dijkstra算法）
• 分数背包问题

2. 活动选择问题详解

活动选择问题是贪心算法的经典应用场景。给定一组活动，每个活动有开始时间和结束时间，如何选择最多的互不冲突的活动？

问题形式化描述：

• 输入：n个活动，每个活动aᵢ有sᵢ(开始时间)和fᵢ(结束时间)
• 输出：最大规模的互不重叠活动子集

2.1 贪心策略选择

常见的三种贪心策略对比：

策略类型	排序依据	是否总能得到最优解	示例反例
最早开始	开始时间	否	[(0,10),(2,3),(4,5)]
最短时长	持续时间	否	[(0,3),(2,5),(4,7)]
最早结束	结束时间	是	-

数学证明： 最早结束策略的正确性可通过归纳法证明：

1. 存在一个最优解包含最早结束的活动a₁
2. 对剩余活动递归应用相同策略

2.2 Python实现与复杂度分析

def activity_selection(start, finish):
    # 将活动按结束时间排序
    activities = sorted(zip(start, finish), key=lambda x: x[1])
    selected = [activities[0]]
    
    for current_start, current_finish in activities[1:]:
        last_finish = selected[-1][1]
        if current_start >= last_finish:
            selected.append((current_start, current_finish))
    
    return selected

# 示例使用
start_times = [1, 3, 0, 5, 8, 5]
end_times = [2, 4, 6, 7, 9, 9]
print(activity_selection(start_times, end_times))

时间复杂度分析：

• 排序阶段：O(n log n)
• 选择阶段：O(n)
• 总体复杂度：O(n log n)

提示：如果活动已按结束时间排序，算法复杂度可降至O(n)

3. 算法优化与变种问题

3.1 资源受限的活动选择

当有多个资源（如会议室）可用时，问题变为将活动分配到最少数量的资源中，使每个资源内的活动不重叠。这可以通过最小堆来高效解决：

import heapq

def min_meeting_rooms(intervals):
    if not intervals:
        return 0
    
    # 按开始时间排序
    intervals.sort(key=lambda x: x[0])
    
    # 用最小堆记录最早结束时间
    heap = []
    heapq.heappush(heap, intervals[0][1])
    
    for interval in intervals[1:]:
        # 当前活动开始时间 >= 堆顶结束时间
        if interval[0] >= heap[0]:
            heapq.heappop(heap)
        heapq.heappush(heap, interval[1])
    
    return len(heap)

3.2 带权重的活动选择

当每个活动有不同的价值，目标是选择总价值最大的不重叠活动集时，问题变得复杂。此时贪心算法可能失效，需要用动态规划解决：

def weighted_activity_selection(activities):
    activities.sort(key=lambda x: x[1])  # 按结束时间排序
    n = len(activities)
    dp = [0] * (n + 1)
    
    for i in range(1, n+1):
        current_val = activities[i-1][2]
        # 找到最后一个不与当前活动冲突的活动
        last_compatible = find_last_compatible(activities, i-1)
        dp[i] = max(dp[i-1], dp[last_compatible+1] + current_val)
    
    return dp[n]

def find_last_compatible(activities, index):
    # 二分查找实现
    low, high = 0, index - 1
    while low <= high:
        mid = (low + high) // 2
        if activities[mid][1] <= activities[index][0]:
            if activities[mid+1][1] <= activities[index][0]:
                low = mid + 1
            else:
                return mid
        else:
            high = mid - 1
    return -1

4. 贪心算法与动态规划对比

贪心算法和动态规划(DP)都是解决优化问题的重要方法，但适用场景不同：

特性	贪心算法	动态规划
最优解	局部最优可能非全局最优	保证全局最优
时间复杂度	通常O(n log n)	通常O(n²)或更高
空间复杂度	通常O(1)	通常O(n)或O(n²)
决策回溯	无回溯	保存子问题解
适用问题	满足贪心选择性质	有重叠子问题和最优子结构

选择建议：

• 当问题具有贪心性质时优先使用贪心算法
• 当需要全局最优解且问题可分解为子问题时使用DP
• 贪心算法通常作为DP的优化手段或启发式方法

5. 实际应用案例

5.1 课程表安排

大学课程表安排是活动选择问题的典型应用。假设有以下课程时间表：

课程	开始时间	结束时间
数学	9:00	10:30
物理	9:30	11:00
化学	11:00	12:00
生物	10:00	11:30
英语	13:00	14:30

使用贪心算法选择最多课程：

courses = [
    ("数学", "9:00", "10:30"),
    ("物理", "9:30", "11:00"),
    ("化学", "11:00", "12:00"),
    ("生物", "10:00", "11:30"),
    ("英语", "13:00", "14:30")
]

def time_to_minutes(time_str):
    h, m = map(int, time_str.split(':'))
    return h * 60 + m

# 转换并排序
activities = [(name, time_to_minutes(start), time_to_minutes(end)) 
              for name, start, end in courses]
activities.sort(key=lambda x: x[2])

selected = [activities[0]]
for name, start, end in activities[1:]:
    if start >= selected[-1][2]:
        selected.append((name, start, end))

print("最多可安排课程:", [name for name, _, _ in selected])

5.2 会议室调度

现代企业会议室资源紧张，使用贪心算法可以最大化会议室利用率。假设某公司有多个会议室和若干会议请求：

meetings = [
    ("产品评审", 9, 10),
    ("技术讨论", 9, 12),
    ("客户会议", 11, 13),
    ("团队站会", 13, 14),
    ("项目计划", 10, 11)
]

meetings.sort(key=lambda x: x[2])  # 按结束时间排序

rooms = [[]]  # 至少一个会议室
for meeting in meetings:
    scheduled = False
    for room in rooms:
        if not room or meeting[1] >= room[-1][2]:
            room.append(meeting)
            scheduled = True
            break
    if not scheduled:
        rooms.append([meeting])

print(f"需要{len(rooms)}间会议室")
for i, room in enumerate(rooms, 1):
    print(f"会议室{i}: {[m[0] for m in room]}")

6. 面试常见问题与解答

6.1 贪心算法解题框架

在技术面试中，解决贪心算法问题通常遵循以下步骤：

1. 问题分析：确认问题是否具有贪心性质
2. 贪心策略设计：确定局部最优的选择标准
3. 正确性验证：证明该策略能得到全局最优解
4. 算法实现：编写高效代码
5. 复杂度分析：评估时间/空间复杂度

6.2 典型面试题解析

问题：给定一组区间，计算需要移除的最小区间数，使剩余区间互不重叠。

解法：这实际上是活动选择问题的另一种表述，可以使用相同的贪心策略：

def erase_overlap_intervals(intervals):
    if not intervals:
        return 0
    
    intervals.sort(key=lambda x: x[1])
    count = 1
    end = intervals[0][1]
    
    for interval in intervals[1:]:
        if interval[0] >= end:
            count += 1
            end = interval[1]
    
    return len(intervals) - count

变种问题：如果区间带权重，需要最大化保留区间的总权重，该如何解决？

此时贪心算法不再适用，需要使用动态规划或记忆化搜索：

def max_weight_no_overlap(intervals):
    intervals.sort(key=lambda x: x[1])  # 按结束时间排序
    dp = [0] * len(intervals)
    dp[0] = intervals[0][2]
    
    for i in range(1, len(intervals)):
        # 当前区间不选
        option1 = dp[i-1]
        # 当前区间选，找到最后一个不冲突的区间
        option2 = intervals[i][2]
        last = -1
        low, high = 0, i-1
        while low <= high:
            mid = (low + high) // 2
            if intervals[mid][1] <= intervals[i][0]:
                last = mid
                low = mid + 1
            else:
                high = mid - 1
        if last != -1:
            option2 += dp[last]
        dp[i] = max(option1, option2)
    
    return dp[-1]

7. 性能优化与工程实践

7.1 大规模数据处理

当活动数量极大（如百万级别）时，可以考虑以下优化：

1. 并行预处理：使用多线程/多进程对活动进行排序
2. 流式处理：如果数据是流式到达，使用在线算法
3. 近似算法：当精确解不必要时可考虑近似贪心算法

# 流式处理版本的贪心算法
def streaming_activity_selection(activity_stream):
    selected = []
    current_end = -float('inf')
    
    for activity in activity_stream:
        # 假设流中的数据已按结束时间排序
        if activity[0] >= current_end:
            selected.append(activity)
            current_end = activity[1]
    
    return selected

7.2 测试用例设计

完善的测试用例应包含：

1. 边界情况：空输入、单个活动、所有活动冲突
2. 特殊分布：完全不相交的活动、完全重叠的活动
3. 随机测试：大规模随机生成的活动集

import random
import pytest

def test_activity_selection():
    # 空输入
    assert activity_selection([], []) == []
    
    # 单个活动
    assert activity_selection([1], [2]) == [(1, 2)]
    
    # 完全冲突的活动
    starts = [1, 1, 1]
    ends = [3, 3, 3]
    assert len(activity_selection(starts, ends)) == 1
    
    # 随机测试
    random.seed(42)
    starts = sorted(random.sample(range(100), 50))
    ends = [start + random.randint(1, 5) for start in starts]
    selected = activity_selection(starts, ends)
    # 验证无冲突
    for i in range(1, len(selected)):
        assert selected[i][0] >= selected[i-1][1]

8. 扩展阅读与学习资源

8.1 推荐学习路径

1. 基础理论：

   • 《算法导论》第16章 - 贪心算法
   • 《算法设计手册》第13章 - 贪心算法

2. 在线课程：

   • Coursera: "Greedy Algorithms" by Stanford University
   • edX: "Algorithmic Design and Techniques" by UCSanDiego

3. 实战平台：

   • LeetCode贪心算法专题
   • Codeforces贪心算法标签题目

8.2 进阶问题探索

1. 区间图着色问题：将区间视为图的顶点，冲突的区间用边连接，求图的最小着色数
2. 动态区间调度：活动可以动态添加和删除，需要维护最优解
3. 多维度贪心：当选择标准涉及多个维度时的权衡策略

# 多维度贪心示例：同时考虑持续时间和开始时间
def multi_criteria_selection(activities):
    # 按持续时间升序，然后按开始时间升序
    activities.sort(key=lambda x: (x[1]-x[0], x[0]))
    selected = []
    last_end = -float('inf')
    
    for start, end in activities:
        if start >= last_end:
            selected.append((start, end))
            last_end = end
    
    return selected