18

给定一个时间间隔列表，我需要找到一组最大非重叠间隔。

例如，

如果我们有以下间隔：

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

还规定时间必须在范围内[0000, 2400]。

最大不重叠的间隔集是[0600, 0830], [0900, 1130], [1230, 1400]。

我知道最大集装箱是 NP-Complete 的。我想确认我的问题（间隔仅包含开始和结束时间）是否也是 NP-Complete。

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

4

1 回答 1

28

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

假设我们有 n 个区间。假设给定的范围是S（在你的情况下，S = [0000, 2400]）。要么假设所有区间都在 范围内S，要么消除所有不S在线性时间范围内的区间。

  1. 预处理：

    • 按开始点对所有区间进行排序。假设我们得到一个包含 n 个区间的数组A[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. 预处理：按它们的端点对所有间隔进行排序。假设我们得到一个包含 n 个区间的数组B[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;
    }
}

以上两个解决方案都是我想到的，但你的问题也称为活动选择问题，可以在维基百科http://en.wikipedia.org/wiki/Activity_selection_problem上找到。

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

于 2013-11-08T03:28:12.940 回答