算法导论第三版16.1-4 贪心算法（区间图着色问题）

本文主要是介绍算法导论第三版16.1-4 贪心算法（区间图着色问题），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

将英文版的答案翻译过来的，互相交流学习，新手轻喷。

假定有一组活动，需要将它们安排到一些教室，任意活动可以使用任意的教室。希望利用最少的教室完成所有活动的安排。

设S是n个活动的集合

利用贪心算法从S中找到一个最大规模的相容集合S1，把他们安排到第一个教室，然后从S-S1中继续找一个最大相

容集合S2，安排到第二个教室。一直这样直到所有活动都被安排，最差需要O（n^2）的时间，而且这样会使得结
果需要更多不必要的教室。
考虑以下活动【1，4】、【2，5】、【6，7】、【4，8】。贪心算法把【1，4】和【6，7】安排在第一个教室，
剩下的【2，5】、【4，8】分别占用一个教室，一共占用了3个教室。但是最优的选择是把【1，4】和【4，8】放
在一个教室，【2，5】和【6，7】放在一个教室，这样只用了2个教室。

考虑一个修正的算法，渐进时间仅仅是需要将活动排序的时间。
一般的思想是把所有的活动按开始时间排序，在允许时间内安排每一个活动。这样需要按照活动时间把整个集合进
行移动。我们建立两个链表，里面放的是教室。一个里面放在当前时刻t被占用的教室（busy），另一个里面放在t时刻没被占用的教室（free）。我们可知，如果Si》=fj，认为i和j是相容的。当t是某个活动的开始时间时，把这个活动
安排到一个空教室，然后把这个教室从free链表转移到busy链表。当t是某个活动的结束时间时，把这个活动所在的教室从busy链表转移到free链表。

如果可能，为了避免使用没必要的教室，总是先使用已经安排过活动的教室，而不使用从未安排过活动的教室。（可以通过把已使用过的空教室放在链表的头部，取教室时从链表头部开始取来实现）

综上，这样可以保证使用尽可能少的教室。直到安排m个教室时，算法终止。此时，让活动i成为教室m的第一个活动只有在时刻Si，前m-1个教室都被安排时，活动i才会被安排在第m个教室。此时，就有m个活动同时发生。因此，任
何安排都至少使用m个教室，这样的安排就是算法最优解。

运行时间：将n个活动按照开始和结束时间排序（有2n个时间），当Si=fj时，先安排活动j。这需要O（nlgn）时间
（最好时间为O（n））。安排每个活动需要的时间为O（n），因为每次移动消耗时间为O（1）。