🧮 贪心算法 (Greedy Algorithm)

难度 / Difficulty: 中等 (Medium)
分类 / Category: 算法优化 (Optimization Algorithm)
时间复杂度 / Time Complexity: O(n log n) 或 O(n)
空间复杂度 / Space Complexity: O(n) 或 O(1)

📖 算法简介 / Introduction

贪心算法是一种在每一步选择中都采取当前状态下最优（即最有利）选择，从而希望最终得到全局最优解的算法思想。贪心算法不考虑整体最优，而是通过局部最优推导全局最优。

Greedy Algorithm is an algorithmic paradigm that makes locally optimal choices at each step with the hope of eventually finding a global optimum. It never reconsiders choices once made, working in a top-down fashion.

💡 算法原理 / Principle

贪心算法的核心是”每步最优，全局可能最优”：

1. 贪心选择 (Greedy Choice)：在每一步选择中都采取当前最优的选择
2. 最优子结构 (Optimal Substructure)：问题的最优解包含其子问题的最优解
3. 不可逆性 (Irrevocability)：一旦做出选择就无法撤销

核心思想：Make the best decision at each step, hoping that local optimal choices lead to a global optimum. Not all problems have this property — only those with “greedy-choice property” and “optimal substructure.”

🔑 关键概念 / Key Concepts

📝 代码实现 / Implementation

# 活动选择问题 - 最多选择不重叠的活动
def activity_selection(activities):
    # 按结束时间排序
    activities_sorted = sorted(activities, key=lambda x: x[1])
    selected = [activities_sorted[0]]
    last_end = activities_sorted[0][1]
    
    for start, end in activities_sorted[1:]:
        if start >= last_end:
            selected.append((start, end))
            last_end = end
    return selected

# 示例
activities = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9), (6, 10), (8, 11)]
print(activity_selection(activities))
# 输出: [(1, 4), (5, 7), (8, 11)]

# 霍夫曼编码 - 最小带权路径长度
import heapq

def huffman_coding(frequencies):
    heap = [[freq, [char, '']] for char, freq in frequencies]
    heapq.heapify(heap)
    
    while len(heap) > 1:
        lo = heapq.heappop(heap)
        hi = heapq.heappop(heap)
        for pair in lo[1:]:
            pair[1] = '0' + pair[1]
        for pair in hi[1:]:
            pair[1] = '1' + pair[1]
        heapq.heappush(heap, [lo[0] + hi[0]] + lo[1:] + hi[1:])
    
    return sorted(heap[0][1:], key=lambda p: (len(p[1]), p[0]))

# 示例
freqs = [('a', 45), ('b', 13), ('c', 12), ('d', 16), ('e', 9), ('f', 5)]
print(huffman_coding(freqs))

🎯 应用场景 / Applications

• 活动安排问题 — 选择最多的不重叠活动
• 霍夫曼编码 — 数据压缩中的最优前缀码
• 最小生成树 — Prim 和 Kruskal 算法
• 单源最短路径 — Dijkstra 算法（正权图）
• 零钱找零 — 在特定面额系统下求最优解
• 区间调度 — 会议室安排、任务分配

📊 复杂度分析 / Complexity Analysis

🏠 实战例题 / Practice Problems

1. LeetCode 455 - 分发饼干 - 简单
2. LeetCode 435 - 无重叠区间 - 中等
3. LeetCode 763 - 划分字母区间 - 中等
4. LeetCode 56 - 合并区间 - 中等