posts - 403, comments - 310, trackbacks - 0, articles - 7
  BlogJava :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

CLRS 习题 16.1-3 Interval-graph Coloring Problem

Posted on 2007-10-14 00:48 ZelluX 阅读(1495) 评论(2)  编辑  收藏 所属分类: Algorithm
问题：
已知一些活动的起止时间{Si}, {Fi}，把它们安排在若干个大厅中进行，要求任一大厅任意时间段内不能有两项活动同时进行，求出所需的最少的大厅数。

分析：(from CLRS Instructor's Manual)

这是一个区间图的着色问题(Interval-graph Coloring Problem)，用点表示活动，把时间冲突的活动连起来，然后进行点的着色，要求同一线段的两端不能有相同颜色的点。

首先最容易想到的就是用书上的Greedy-Activity-Selector找出可安排在大厅1的最长序列，然后删去这些活动，再次调用该方法，找出安排在大厅2的活动，以此类推。
复杂度O(n*n)

还有一个O(n*logn)的算法，甚至在起止时间都是比较小的数字时复杂度只有O(n)。

主要思想是依次遍历每个活动，把它们安排到不同的大厅中。
维护两张表，一张记录当前时间t已经安排了活动的大厅，另一张记录当前时间空闲的大厅
然后从头扫描排序后的时间点序列（如果事件a的结束时间等于时间b的开始时间，那么前者应该排在后者后面）
碰到开始时间t，把该活动放到空闲列表的第一个大厅中（如果空闲列表为空则新加一个大厅），然后把该大厅放入已安排的大厅列表中；
碰到结束时间t，从已安排的大厅列表中移出相应大厅到空闲列表。

复杂度分析：
排序：O(n logn)，如果时间范围有限制还可以做到O(n)
处理：O(n)

评论

# re: CLRS 习题 16.1-3 Interval-graph Coloring Problem  回复  更多评论   

2007-12-12 11:11 by clseeyou
活动选择问题只是求解相容活动的最大数量,如下:
解为2,最优解为(1)(3)
(1) ---
(2)-----
(3) --
(4) ----
如果用你所说的方法求解区间图着色问题,那么解为3:{(1)(3)}{(2)}{(4)}
明显可以看出最优解为2:{(1)(4)}{(2)(3)}
该算法还是有问题的```

# re: CLRS 习题 16.1-3 Interval-graph Coloring Problem  回复  更多评论   

2007-12-12 11:59 by ZelluX
我没说后面是区间图的着色问题的解法啊 @.@
只是前面提了一下而已

只有注册用户登录后才能发表评论。
网站导航: