最大非重叠的时间间隔中一个间隔树 [英] Maximum non-overlapping intervals in a interval tree

问题描述

由于时间间隔的列表，我需要找到该组最大非重叠的时间间隔

Given a list of intervals of time, I need to find the set of maximum non-overlapping intervals.

例如，

如果我们有如下的时间间隔：

if we have the following intervals:

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

此外，它被赋予的时间都在范围 [0000，2400] 。

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

据我所知，最大的集装箱是NP完全问题。我想确认，如果我的问题（只包含开始和结束的时间间隔）也是NP完全问题。

I understand that maximum set packing is NP-Complete. I want to confirm if my problem (with intervals containing only start and end time) is also NP-Complete.

如果是的话，有没有办法找到指数时间的最佳解决方案，但聪明preprocessing和修剪的数据。或者，如果有一个比较容易实现的固定参数可解算法。我不想去一个近似算法。

And if so, is there a way to find an optimal solution in exponential time, but with smarter preprocessing and pruning data. Or if there is a relatively easy to implement fixed parameter tractable algorithm. I don't want to go for an approximation algorithm.

推荐答案

这是不是一个NP完全问题。我能想到的 0的（N *的log（n））使用动态规划来解决这个问题的算法。

This is not a NP-Complete problem. I can think of an O(n * log(n)) algorithm using dynamic programming to solve this problem.

假设我们有N个间隔。假设给定的范围是取值（在你的情况， S = [0000 2400] ）。无论是料想所有间隔取值中，或消除所有的时间间隔不取值中的线性时间。

Suppose we have n intervals. Suppose the given range is S (in your case, S = [0000, 2400]). Either suppose all intervals are within S, or eliminate all intervals not within S in linear time.

1. pre-过程：

1. Pre-process:

• 排序所有间隔由他们开始点。假设我们得到N个间隔的数组 A [N] 。
  • 在这一步需要 O（N *的log（n））时间
  • Sort all intervals by their begin points. Suppose we get an array A[n] of n intervals.
    • This step takes O(n * log(n)) time
    • 如果这样的开始点区间的终点我，我们可以指定 N 来不存在下一页[I] 。
    • 我们可以在做到这一点为O（n *的log（n））通过枚举ñ结束所有的间隔点，并使用二进制搜索来找到答案的时间。也许存在着解决这一线性的方法，但它并不重要，因为previous一步已经采取 O（N *的log（n））的时间。
    • If such begin point does not exist for the end point of interval i, we may assign n to Next[i].
    • We can do this in O(n * log(n)) time by enumerating n end points of all intervals, and use a binary search to find the answer. Maybe there exists linear approach to solve this, but it doesn't matter, because the previous step already take O(n * log(n)) time.

    DP：

    • 假设最大非重叠的区间范围内 [A [1] .begin，S.end] 是 F [I] 。然后 F [0] 是我们想要的答案。
    • 另外，假定 F [N] = 0 ;
    • 在状态转移方程：
      • F [i] = {最大值F [I + 1]，1 + F [下一页[我]]}
      • Suppose the maximum non-overlapping intervals in range [A[i].begin, S.end] is f[i]. Then f[0] is the answer we want.
      • Also suppose f[n] = 0;
      • State transition equation:
        • f[i] = max{f[i+1], 1 + f[Next[i]]}

        以上的解决方案是一个我想出这个问题的第一眼。在那之后，我也想了一个贪婪的方法是简单（但在大O符号的意义不是更快）：

        The above solution is the one I come up with at the first glance of the problem. After that, I also think out a greedy approach which is simpler (but not faster in the sense of big O notation):

        （与相同的符号，并假设如上述的DP方法）

        (With the same notation and assumptions as the DP approach above)

        1. pre-过程：由他们的结束分排序的所有区间。假设我们得到一个数组 B [N] N个间隔的。

        1. Pre-process: Sort all intervals by their end points. Suppose we get an array B[n] of n intervals.

        贪婪的：

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

      以上两种解决方案，从我的脑海里走出来，但你的问题也被称为在活动选择问题，它可以在维基百科<一个被发现href="http://en.wikipedia.org/wiki/Activity_selection_problem">http://en.wikipedia.org/wiki/Activity_selection_problem.

      The above two solutions come out from my mind, but your problem is also referred as the activity selection problem, which can be found on Wikipedia http://en.wikipedia.org/wiki/Activity_selection_problem.

      此外，算法导论的讨论在16.1深入这个问题。

      Also, Introduction to Algorithms discusses this problem in depth in 16.1.

      这篇关于最大非重叠的时间间隔中一个间隔树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！