区间树中的最大非重叠间隔

Question

给定一个时间间隔列表,我需要找到最大非重叠间隔的集合.

例如,

如果我们有以下间隔:

[0600, 0830], [0800, 0900], [0900, 1100], [0900, 1130], 
[1030, 1400], [1230, 1400]

另外,时间必须在该范围内[0000, 2400].

最大非重叠间隔集是[0600, 0830], [0900, 1130], [1230, 1400].

我知道最大设定包装是NP-Complete.我想确认我的问题(包含仅包含开始和结束时间的间隔)是否也是NP-Complete.

如果是这样,有没有办法在指数时间内找到最佳解决方案,但有更智能的预处理和修剪数据.或者如果有一个相对容易实现的固定参数易处理算法.我不想去寻找近似算法.

Answer 1

这不是NP完全问题.我可以想到一个O(n * log(n))使用动态编程来解决这个问题的算法.

假设我们有n个区间.假设给定范围是S(在您的情况下S = [0000, 2400]).假设所有间隔都在S,或者消除不S在线性时间内的所有间隔.

1. 前处理:

   • 按起点对所有间隔进行排序.假设我们得到一个A[n]n个区间的数组.
     • 这一步需要O(n * log(n))时间
   • 对于所有间隔的终点,找到其后的最小起点的索引.假设我们得到一个数组Next[n]的n整数.
     • 如果对于间隔的终点不存在这样的开始点,i,我们可以分配n给Next[i].
     • 我们可以O(n * log(n))通过枚举所有间隔的n个端点来及时完成此操作,并使用二进制搜索来查找答案.也许存在线性方法来解决这个问题,但这并不重要,因为上一步已经花费了O(n * log(n))时间.

2. DP:

   • 假设范围内的最大非重叠区间[A[i].begin, S.end]是f[i].那f[0]就是我们想要的答案.
   • 还假设f[n] = 0;
   • 状态转移方程:
     • f[i] = max{f[i+1], 1 + f[Next[i]]}
   • 很明显DP步骤需要线性时间.

上面的解决方案是我在问题的第一眼看出来的那个.在那之后,我也想出了一个更简单的贪婪方法(但在大O符号意义上并不快):

(使用与上述DP方法相同的符号和假设)

1. 预处理:按其终点对所有间隔进行排序.假设我们得到一个B[n]n个区间的数组.

2. 贪婪:

   int ans = 0, cursor = S.begin;
   for(int i = 0; i < n; i++){
       if(B[i].begin >= cursor){
           ans++;
           cursor = B[i].end;
       }
   }
   

上面两个解决方案出自我的想法,但您的问题也被称为活动选择问题,可以在Wikipedia http://en.wikipedia.org/wiki/Activity_selection_problem上找到.

此外,算法简介在16.1中深入讨论了这个问题.