Snowdream

I'm awake but my world is half asleep
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 阅读(1351) 评论(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
我没说后面是区间图的着色问题的解法啊 @.@
只是前面提了一下而已

只有注册用户登录后才能发表评论。


网站导航: