开了一算法专栏，整理了我当大学助教和面试算法的过程中，比较有意思的话题。预计每隔周出一篇原创文章，更新于微博/知乎/公主号@甜菜欣欣，欢迎反馈意见，共同交流学习。

当代年轻人，面临的一大难题就是拖延症。

想到有那么多事情要做，赶紧刷会儿手机压压惊。任务总是拖到最后一刻，相信自己一定能急中生智化险为夷。逃避可耻但有用，一言不合就通宵。截止日期的前一晚，效率高到突破天际。

那么，这样的时间安排到底合理吗？最后一刻突如其来的求生欲，能会给你最高的效率吗？算法告诉你答案。

首先，对问句里的概念下个更为精确的定义——

假设现在有n个任务，每个任务完成的时间是一个单位的时间（比如一小时），分别有对应的截止时刻，还有按时完成所能获得的分数（一个大于零的实数）。如果一个任务在截止时刻前被完成，就能累计对应的分数，否则不加分。现在要安排这些任务在整数的时间点开始，每个单位时间最多只能进行一项任务，求一种算法能解出最优的计划，得到最多的分数。

某拖延症欣欣给出的算法如下——

首先，按分数高低给任务排序。然后从分值最高的任务开始，对于每个任务，都分别安排在任务截止时刻前的最后一个空闲的单位时间块里。

先说结论。这个拖延症算法，解出来的结果是最优的。也就是说，这个计划确实能安排得下最多的任务。惊不惊喜，意不意外？

有的朋友可能看出了，这个算法属于贪心算法（Greedy Algorithm），即每一步都只考虑当前情况下最优的选择。就好像去吃自助餐的时候，先跑去吃最好吃的东西一样；或者找给别人零钱的时候，先给十块钱的纸币，剩下的用五块钱，然后一块钱和硬币，最为方便。

当贪心算法满足下面两个条件，就能得到问题的整体最优解——

1）贪心选择性质（Greedy-Choice Property）：问题的整体最优解可通过不断选择局部的最优解来得到；

2）最优子结构性质（Optimal Substructure）：问题的整体最优解包含了它的子问题的最优解。

回到由欣欣命名的拖延症算法。直觉的解释是，时间越靠前越宝贵，所以要优先安排最贵的任务，又不舍得安排到最前面耽误了其它稍便宜的任务，那就优先安排但尽量安排得晚一些。而贪心算法的严谨证明，还需多花一点力气。

为了简化问题，只考虑那些把时刻0到时刻n都排满的计划。因为任何的最优解，必然是从一开始就排满的。如果一个计划在时刻0到时刻n有空闲的时间块，那么把时刻n以后的任务往前填，必然只会增加按时完成的任务数量和分值，得到更优的解。

于是问题被简化成了只有n个任务和n个时间块，注意任务数和时间块的数量相等了。假设题目允许不把一个任务安排到任何时间点，因为任务无论如何都无法按时完成的话安排便无意义，但方便起见我们还是把这个任务放置到最末的空闲时间块。

我们锁定一个最优解的安排，方便起见将其标记为Q。

第一步，证明“贪心选择性质”成立。需要证明对于任何一个情况，如果把分值最高的任务叫做T，把T被拖延算法安排到的时间块记作t，那么存在某个最优解Q*把任务T安排到了时间t。

证明开始。如果在最优安排Q*里，任务T已经被安排到了时间t，那么啥也没做上面那句话就成立了。否则若时间t安排了另一个任务T’，而任务T被安排到了另一个时间t’，我们则可以构造一个新的解Q’，在这个解里交换任务T和T’的位置。然后分类讨论来证明Q’也是最优解：

情况一，时间t早于任务T的截止时刻，且在安排Q*里任务T得到了按时完成的加分。那么时间t’早于t，因为任务T’已经被安排到了再晚就没有加分的时间。交换T和T’之后，根据分类条件T仍有加分，而T’更早完成了，总分值只会增加而不会降低。

情况二，时间t早于任务T的截止时刻，且在安排Q*里任务T没有得到加分，那么时间t’要晚于t。交换T和T’之后，最坏结果是错过了低分值任务却额外获得了高分值，任务总分值只会增加而不会降低。

情况三，时间t晚于任务T的截止时刻，那么说明任务的截止时刻前没有空余时间了，任何安排都无法得到任务T的分值。而根据算法，t是最后一个空余的时间块，所以t’早于t。交换任务使得低分值任务T’被提到更前面，有可能额外得到任务T’的分值，总分值可能增加而不可能降低。

所以Q’在这三种情况下都是最优解，而Q’任务T安排到了时间t。每当我们做出一个贪心选择，都会得到一个完全独立不受限制的子问题，直到算法结束。第一步证毕。

第二步，证明“最优子结构性质”成立。把一个任务安排到一个时间块，剩下的任务和剩下的时间块就可组成一个子问题。我们需要证明，如果在（n-1）个任务和（n-1）个时间块组成的子问题里已有最优的计划，那么把额外的一个任务安排在额外的一个时间块，所得到的还是最优的计划。

这部分证明更短一些。假设子问题里的某个计划能得到分值S，而最优计划能得到分值S*；在更大的问题里多安排一个任务能总共得到T，而最优计划能得到分值T*；把额外的那个任务安排在额外的那个时间块能得到的分数标记为B。

T = B + S （对于任一计划）
T* = B + S* （对于最优计划）

已知S ≤ S*，所以T ≤ T*。最优计划还是最优计划，就是没办法。

至此我们证明了，拖延症算法能让我们完成最多最重要的事情。当然，实际生活中最好还是不要把事情拖到最后一刻去做，现实往往是一个任务没做就完蛋了，唯一的方法是使劲做。

如果给上面那个问题稍加变化，每个任务不是单位时间而是可以为任意整数时间长度，猜猜看还能用贪心来解吗？这道题被收录在Leetcode #253 会议室二（Meeting Room II），是最为经典的算法面试题之一。以后有时间补充证明思路～

关于贪心算法，最后简短提几个点。

1）贪心算法不是某个具体的算法，而是一大类算法的总称。粗略地说，凡是啥也不管狂在局部选最优解的都可称作贪心算法。

2）能用贪心算法解决的问题，当前决策必须不能对之前的选择有依赖，只可和当前的状态有关。往往问题的不同部分之间关系不太紧密，尤其是时序上的关系。

3）贪心算法的“最优子结构性质”很多时候容易和动态规划（dynamic programming）里的概念弄混。如果没有听说过动态规划，不用慌，可先跳过这段。动态规划和贪心算法非常不一样，动态规划会同时计算互斥的一些状态，而贪心永远只有一种状态、一种可能性，并且不会撤销回到之前的状态。

4）贪心算法作为基础算法思想，不仅在生活中，在计算机世界里也有广泛的应用。一个比较经典的例子是哈夫曼编码(Huffman Coding)，根据字符出现的频率构造出一棵二叉树，然后用它来压缩数据，非常酷炫。