本文主要是介绍区间图着色问题（算法导论课后题目16.1.3），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
这个问题是《算法导论》里面的习题。
问题的描述是这样的：有n个活动，对于其中的每个活动Ai均有一个开始时间Si和结束时间Fi表示该活动的举办时间是[Si, Fi), 其中0 <= Si < Fi < MAX。现在我们希望使用尽可能少的教室来调度所有的活动。注意每个活动在其举办时间内都独占公共的资源（比如教室等），所以一个教室同一时间只能有一个活动。
为了与活动选择问题区别，我们将该问题成为活动全选择问题。
等价的描述一：活动全选择问题模型可以转化成一个区间图，其顶点为活动，如果两个活动不兼容则在其对应的顶点上连一条边。为使任两个相邻结点的颜色互不相同，所需的最少颜色数对应于找出调度给定的所有活动所需的最少教室数。这个问题就是经典的区间图着色问题(interval-graph-coloring-problem)。
等价的描述二:n条线段，每条线段都有起点S和终点F。现在将这n条线段分为尽量少的组，且每组的线段段互不重叠。求这个组数。
下面给出一些可行的解题算法。
贪心算法一:最容易想到的算法是使用活动选择问题的思路，找出可安排在大厅1的最长序列，然后再剩余的活动中找出安排在大厅2的活动，以此类推，知道所有活动都被安排了为止。该算法复杂度是O(n*n).
贪心算法二: 对于活动的开始时间和结束时间点进行排序。初始两个集合busySet和freeSet为空。扫描排序的时间t，若t为一个活动的开始时间，则从freeSet中取出一个教室加入busySet(如果freeSet为空则新加一个大厅）。若t为一个活动的结束时间，从busySet中移出该活动使用的大厅到freeSet。当我们不关心是具体哪个教室去搞哪个活动的时候，我们可以不用集合busySet和freeSet，而用一个整数busyNum表示目前使用的教室数，当新增一个活动时则busyNum++,否则busyNum–.这个过程中最大的busyNum即为答案。当排序我们使用快速排序是，算法复杂度是O(nlogn) + O(2n)，即O(nlogn)。
这篇关于区间图着色问题（算法导论课后题目16.1.3）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
