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