贪心算法啊，以前老是以为它没什么技术含量，上不了台面。长时间下来，也就养成了“不可能是贪心这么简单”的思维习惯，遇到问题时几乎不会往贪心的方向想。

    可是谁料到最近一下就被我碰到了两道贪心题，改变了我对贪心的观点。其中一题我在上一篇就讲过了，是 2008 年 TUDPC 的第 E 题。还有一题就是 PKU 3110。

    题意是说有 N 门考试（N ≤ 50,000），各门考试的日期跨度大约不超过 73,000 天（这个故事好像有点不符合现实，但是毕竟是题目嘛）；每门课都需要一天的时间复习；两门课不能在同一天复习；有考试的日期不能复习功课；每门考试都有一个复习的时间下限，即复习的日期不能早于考试的前若干天，否则到考试时会忘掉；如果要通过所有考试，问可以最晚开始复习的日期（即第一个复习的日期要尽量的晚）是哪天。

    我开始还在往最大匹配上想，每门考试是左边的一个节点，每个日期是右边的一个节点，每门考试对应有限的几个日期，每个日期只能有一门考试。整个模型乍看有点像样，但是看看数据规模就知道不可能了。况且这样算不出最晚开始复习的日期。

    后来得知了可以用贪心解决，算法很简单：把所有考试从晚到早排序，从最晚的考试日期开始倒数；如果当天有考试，则把这些考试的复习时间下限放进一个优先队列；如果当天没有考试，则从优先队列里取出下限最晚的一个，把它复习掉；如果从优先队列里出来的这个时间下限已经比当天晚了，则无解。

    不难证明，这样得到的是最优解。假设一天没有考试，优先队列里时间下限最晚的一门考试是 A，但是当天没有复习这一门，而是复习了下限较早的考试 B。如果这样最终得到了最优解，那么，即然 A 的下限比 B 的晚，则互换 A 和 B 的复习日期是合法的，而且同样是最优解。也就是说，以上算法可以得到最优解。□

    以上这两道贪心的题目都是和工作流程之类的沾点边的，看来以后碰到这种题的时候要多长个心眼了。