区间图着色问题(Interval-graph coloring) 调度所有区间

问题：

 用很多教室对一组活动进行调度，希望所用的教室数最少。

 

算法：

 

对活动时间按开始、结束时间排序（2n个元素）。

 

建立2个list，第一个list放已使用过的教教室，记做BusyList ，第二个list放未使用的教室FreeList ，

 

 

对某个时间t，

1. 如果t是某活动 i 的开始时间，在未使用的教室FreeList 中选择教室给 i ，然后把该教室加 入到已使用的教室BusyList 中，如果FreeList 中没有教室，则新生成一个教室，并把该教室加入到BusyList 中

 

2. 如果t是活动i 的结束时间，则把BusyList 中，分配给t 的教室删除，加入到FreeList 中去。

 

时间复杂度：

 

O(2n）+O(排序的时间）=O(N)+O（NlgN） ，如果n很小的话，可以用计数排序，复杂度可降为O(N).

 

注：1.感觉算法还是不太好写的。

       2.和算法导论上的解法有点不一样。 算法导论上说FreeList存储所有教室，包括分配过的和未分配过的。