这是 O（nlog n）时间，O（n）空间 算法。首先，如果元组数组尚未按此顺序排列，则按其起始位置对其进行排序。我假设从零开始的数组索引。

让我们调用元组ib（i）的开始位置和结束位置e（i），以使其总长度为e（i）-b（i）+1。还要定义一个函数next（i），该函数返回第一个元组的元组列表中的位置，可以显示在元组i的右侧。注意，可以使用二进制搜索在O（log
n）的时间内计算next（i）：只需将所有元组的起始位置b（i）保留在数组b []中，然后在子数组b [中搜索第一个j i + 1 .. n-1]的b
[j]> e（i）。

让我们将f（i）定义为 在 元组i 或之后 开始的任何不重叠元组的最大覆盖率。由于元组i本身是否处于此最佳集合中，因此我们具有：

f(i) = max(e(i) - b(i) + 1 + f(next(i)), f(i+1)) for 0 <= i < n

我们还有边界条件f(n) = 0。

显然，最大可能的覆盖范围由f（0）给出。这很容易计算。在伪C ++中：

int b[] = /* Tuple beginning positions, in nondecreasing order */;
int e[] = /* Tuple end positions */;
int n = /* Number of tuples */;

// Find the array position of the leftmost tuple that begins to the right of
// where tuple i ends.
int next(int i) {
    return upper_bound(b + i + 1, b + n, e[i]);
}

int maxCov[n + 1];    // In practice you should dynamically allocate this

// After running this, maxCov[i] will contain the maximum coverage of any
// nonoverlapping subset of the set of n - i tuples whose beginning positions
// are given by b[i .. n-1] and whose ending points are given by e[i .. n-1].
// In particular, maxCov[0] will be the maximum coverage of the entire set.
void calc() {
    maxCov[n] = 0;
    for (int i = n - 1; i >= 0; --i) {
        maxCov[i] = max(e[i] - b[i] + 1 + maxCov[next(i)], maxCov[i + 1]);
    }
}

循环calc()运行n次，并且每次迭代都会对二进制搜索函数进行一次O（log n）调用upper_bound()。

我们可以通过计算f（0）的max（）的两个输入，查看哪个实际产生了最大值，记录是否暗示着元组0的存在，然后递归处理该大小，来构造一个实际大小的集合。余数（对应于f（next（0））或f（1））。（如果两个输入相等，那么会有多个最优解，我们可以遵循其中一个。）