CLRS16.1-3 interval-graph coloring problem

565阅读 0评论2010-01-25 wqfhenanxc_cu
分类:C/C++

有一系列活动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中。
上一篇:0-1背包问题
下一篇:转载 trie数据结构