Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1063584
  • 博文数量: 242
  • 博客积分: 10209
  • 博客等级: 上将
  • 技术积分: 3028
  • 用 户 组: 普通用户
  • 注册时间: 2008-03-12 09:27
文章分类

全部博文(242)

文章存档

2014年(1)

2013年(1)

2010年(51)

2009年(65)

2008年(124)

我的朋友

分类: C/C++

2010-01-25 19:51:27

有一系列活动1、2、3....n,知道它们的开始时间s[i]和结束时间e[i],
求至少安排多少个活动地点才能让这些活动不互相冲突?

书中把这类问题抽象为interval-graph coloring problem,但我们这里就具体问题具体分析,不涉及整个
区间图着色问题的解法。

O(n^2)解法:
  按e[i]进行排序,然后按CLRS16.1节所用的greedy algorithm每次选取最多活动给一个活动地点,
    排序O(n*logn);
    每次greedy algorithm O(n),最坏情况下会使用n次greddy algorithm, O(n^2);
  故总的时间复杂度O(n^2).

O(n*logn)解法:
  将s[1]、e[1]、s[2]、e[2]、....s[n]、e[n]全部放到一块排序,并标示一个时间是哪个事件的时间,也要标示一个时间是开始时间还是结束时间。
   若只是要求出最大活动地点数目,下面可以简单地这么写:
       nColorUsing = 0, MaxColor = 0;
       for i in 1 to 2n
           if TimePoints[i].type == "Begin"
               nColorUsing++;
               if nColorUsing > MaxColor
                   MaxColor = nColorUsing;
           else TimePoints[i].type == "End"
               nColorUsing--;
       print MaxColor;

   若是要求出一个活动分配给各个活动地点的情况,维护两个活动地点列表free_locate和basy_locate,
每个活动地点有编号,从1开始往上增加。 遍历TimePoints数组,碰到开始时间,就从free_locate表中找一个放入busy_locate,并为该开始时间所对应的活动i记录分配的活动地点编号;如果free_locate为空了,就新分配一个活动地点,并用全局变量max_Locate++。 碰到结束时间,就从busy_locate表中将相应的活动地点放到free_locate中。
阅读(1762) | 评论(0) | 转发(0) |
0

上一篇:0-1背包问题

下一篇:转载 linux 热键

给主人留下些什么吧!~~