# 贪心算法

1. 活动选择问题
   - 问题描述：有一系列活动，每个活动有开始时间和结束时间，要求选择最多不相交的活动数
   - 可以考虑使用动态规划，因为可以找到最优子结构，总的时间复杂度为 $O(n^2\log n)$，使用 $T(s_i,f_j)$ 表示从 $a_i$ 的开始时间到 $a_j$ 的结束时间中最多的活动数，考虑选与不选 $a_i$，一共 $O(n^2)$ 个值，每个值计算需要 $(\log n)$ (考虑在最初建一棵 BST，时间复杂度为 $O(\log n)$)
   - 发现最早结束的活动一定是某个最优解的一部分，否则可以把一个最优解中的结束最早的活动替换成整体中最早结束的活动，且满足不会出现冲突，个数也不会减少，因此可以对结束时间排序，然后依次选择不冲突的活动，时间复杂度为 $O(n\log n)$

2. 给定磁带上的 $m$ 个文件，每个文件大小不同，分别为 $l_1,l_2,\ldots,l_m$，每个文件的读写频率为 $\frac{1}{m}$，求如何放置这些文件
   - 应该把文件按大小排序，然后依次放入磁带，这样可以使得平均读写时间最小
   - 如果频率不同，则应该按 $l_i/f_i$ 从小到大排序

3. 贪心的要求：每一步选择都是安全的，是某个最优解的一部分，一样要有最优子结构，即一个子问题的最优解即原问题的最优解
   - 贪心选择性
   - 最优子结构

4. 哈夫曼编码
   - 问题描述：给定一个字母表，每个字母的出现频率为 $f_i$，求如何编码使得总的编码长度最短
   - 贪心选择：每次选择两个频率最小的字母，合并成一个新的字母，频率为两者之和，直到只剩一个字母
   - 数据结构：最小优先队列

5. 拟阵属性 Matroid $\subset$ Greedoid
