下面是一个 O（n日志N） - 时间，为O（n）空间算法。首先，他们的起始位置排序元组的数组，如果他们不是已经在这个顺序。我假设从零开始的数组下标。

Here is an O(nlog n)-time, O(n)-space algorithm. First, sort the array of tuples by their starting position if they are not already in this order. I'll assume zero-based array indices.

让我们称之为元组IB（i）和结束位置E（i）的开头位置，使得其总长度为e（ⅰ） - B（1）+1。此外，让我们定义一个函数下（ⅰ）该返回可以出现元组我的右手侧的第一元组的元组列表内的位置。请注意，下一个（我）可以在O计算（log n）的时间与二进制搜索：只要保持所有元组中的数组b []开始位置B（1），并搜索子阵列B〔第j个I + 1 .. N-1]其B〔J]> E（I）。

Let's call the beginning position of tuple i b(i) and the ending position e(i), so that its total length is e(i) - b(i) + 1. Also let's define a function next(i) that returns the position within the tuple list of the first tuple that can appear to the right-hand side of tuple i. Notice that next(i) can be calculated in O(log n) time with a binary search: just keep all the tuple beginning positions b(i) in an array b[], and search for the first j in the subarray b[i+1 .. n-1] having b[j] > e(i).

让我们定义F（i）有任何不重叠的元组集开始于或之后的元组我的最大覆盖范围。由于元组我本身就是无论是在本组***与否，我们有：

Let's define f(i) to be the maximum coverage of any nonoverlapping set of tuples that begins at or after tuple i. Since tuple i itself is either in this optimal set or not, we have:

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

我们也有边界条件 F（N）= 0 。

显然可能的最大覆盖范围为F（0）。这是很容易计算出来。在伪C ++：

Clearly the largest possible coverage is given by f(0). This is easily calculated. In pseudo-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]);
    }
}

在环路计算（）运行n次，并且每次迭代让人O（log n）的调用二进制搜索功能 UPPER_BOUND（ ）。

The loop in calc() runs n times, and each iteration makes one O(log n) call to the binary search function upper_bound().

我们可以通过计算两个输入到最大重建这种规模的实际集合（）对于f（0），其中的一个实际产生的最大，记录是否意味着元组0的presence或不存在观光，然后迭代处理余数（对应于任一F（下（0））或f（1））。 （如果两个输入相等，则有多个最优的解决方案，我们可以按照任何一个。）

We can reconstruct an actual set of this size by calculating both the inputs to max() for f(0), seeing which one actually produced the maximum, recording whether it implies the presence or absence of tuple 0, and then recursing to handle the remainder (corresponding to either f(next(0)) or f(1)). (If both inputs are equal then there are multiple optimal solutions and we can follow either one.)