贪心思想 ——別人恐懼我貪婪 // My Prejudice

本文证明严格不超过三句话。

此类问题的证明思路，一般是证明该方法至少不会比最优方案更差即可。证明较为简单。

定义：数轴上有n个区间，选择最多的区间使之互不重叠

算法：按右端点排序，依次选取能选择的最小右端点的区间

定义：有一组活动，每个活动举办时间为(区间)[Si, Fi]，选取最少的教室(资源)能够满足所有活动如期举行。
简略证明：显然最少的教室至少为最大的区间的重叠层数d。由d的定义可以证明，按照左端点排序后依次分配每个区间给d个资源，每个区间都能被分配到一个其所在区间还没被占用的资源。

算法：（平衡树实现）

按左端点排序，利用前缀和计算d(左端点+1，右端点-1)。每个区间在分配时只需找到可以放置的资源即可直接放置。

按右端点排序，通过逆向来计算d，正向分配区间时，每次找出可以放置的资源中最大右端点的资源进行放置。

定义：某人（资源）有一组任务（区间），每个任务有各自固定的花费时间和最终期限。若任务完成时间超出最终期限，超出部分记为延迟时间，求最少延迟时间。
贪心直觉：每个任务都在最终期限时刚好完成，其效果最好，因为能最大限度不阻挡其他任务的完成，只需再满足任务之间不重叠即可。可以证明这是正确的。

算法：将每个任务按照最终期限大小依次排序，中间不能有空区间。

拓展：找出最多符合最终期限的区间并且个数相同的情况下取完成这些任务的最快方案。（dp）

定义：一系列的区间，选择最少的区间覆盖指定线段[s,t]

算法：按区间左端点排序后，每次取与前一区间有交集并且右端点最大的区间。

定义：点在区间内则可以形成一对匹配关系。现有一系列点和区间，最多能够形成多少对匹配关系。

算法：将点按顺序排序后，每次在剩余的区间中选择覆盖该点的并且右端点最小的区间。

类似抽象代数一般，通过总结一部分贪心算法的本质点，1935年美国数学家Whitney首先提出了拟阵的概念。将这一类贪心问题抽象化成拟阵上的问题。

定义：拟阵(matroid)是一个序偶 $M = (S, \Gamma)$

$S$为一个有穷集合
$\Gamma$ 为S的子集组成的一个非空族，这些子集成为S的独立子集，满足若 $B \in \Gamma$ 且 $A \subseteq B$，则有$A \in \Gamma$。这个性质称为遗传性。
若$A \in \Gamma, B \in \Gamma$，且$|A| < |B|$，则$\exists x \in B-A$，使得$A \cup {x} \in \Gamma$。这个性质称为交换性。

推导出来的性质：

若$A \in \Gamma$，则A的所有子集均属于$\Gamma$。（遗传性的等价条件）
若$A \in \Gamma, B \in \Gamma$，且$|A| < |B|$，则$\exists S \subseteq B-A$，使得$|A \cup S| = |B|$，并且再由性质2得到，$ \forall T \subseteq S, T \in \Gamma $。

参考文献：