间隔树中的最大不重叠间隔

这不是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))

     时间。

   • 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中深入讨论了这个问题。