贪心算法例子

贪心算法概述

贪心算法是一种在每一步选择中都做出局部最优选择的算法，以期望通过一系列局部最优选择达到全局最优。贪心算法在许多优化问题中表现良好，特别是在某些特定类型的问题中能够保证找到最优解。

• 活动选择问题（Activity Selection Problem）
• 背包问题（贪心解法）
• 霍夫曼编码（Huffman Coding）
• 最小生成树（MST, Minimum Spanning Tree）
  以下是几个经典的贪心算法示例：

1. 活动选择问题（Activity Selection Problem）

活动选择问题是指给定一组活动，每个活动有一个开始时间和结束时间，选择尽可能多的活动，使得它们互不冲突。

• 时间复杂度：O(nlogn)

def activity_selection(start, end):n = len