我有一个问题，这是非常相似的algorithm找到最长的非重叠序列的。

I have a question that is very similar to algorithm to find longest non-overlapping sequences.

唯一的区别链接的问题，而不是寻找一套不重叠的元组重新present在最长的序列，我需要找到一套非重叠元组那些重新present在最大覆盖范围，我指的的的元组的长度之和的是最大的（一个的元组的长度的是最后 - 第一+ 1 给出的定义的元组的，在一个句子）

The only difference to the linked question is that instead of finding the set of non-overlapping tuples that represent the longest sequence, I need to find the set of non-overlapping tuples that represent the maximum coverage, by which I mean the sum of the tuple lengths is maximum (a tuple length being last - first + 1 given the definition of tuple in the next sentence).

我重新present我的元组不同于链接的问题。而不是（起始索引，长度），我重新present我的元组为（第一个，最后一个）;例如，元组（3,7）重presents该组数字中 [3，4，5，6，7] 。 （一元组的重叠的另外一个元组，即使终点的比赛，也就是说，（2,6）和（6 ，8）的重叠的，因此不能同时出现在该溶液中。）

I represent my tuples differently than the linked problem. Instead of (starting index, length), I represent my tuples as (first, last); for example, the tuple (3,7) represents the set of numbers [3, 4, 5, 6, 7]. (A tuple overlaps another tuple even if the end-points match; i.e., (2,6) and (6,8) overlap and therefore cannot both appear in the solution.)

作为一个例子，考虑下面的元组集，排序第一：

As an example, consider the following set of tuples, sorted by first:

[（0,100），（2,50），（30,150），（60,95），（110190），（120,150），（191200）]

的最大此处设置将 [（0,100）（110190），（191200）] 与 101 + 81 + 10的覆盖= 192 。 （注意，在此溶液中的元组的非重叠的。）

The maximal set here would be [(0,100), (110,190), (191,200)] with a coverage of 101 + 81 + 10 = 192. (Note that the tuples in this solution are non-overlapping.)

这是最不复杂的算法的一个例子，以解决这个问题，并且什么是该算法的复杂？ （这将是好了，如果这可以在 O（N解决），但我不知道它是否能一时看。）

What is an example of the least complex algorithm to solve this, and what is the complexity of that algorithm? (It would be just great if this could be solved in O(N), but I don't know at the moment if it can be.)

附录：现在回想起来，事实证明，我问这里的问题是等同于的 加权区间调度问题 。这是区间调度问题的一个特例。

ADDENDUM: In retrospect, it turns out that the question I am asking here is equivalent to the weighted interval scheduling problem. This is a special case of the interval scheduling problem.

@ j_random_hacker的回答，下面，是的，其实，已知的解决方案，以加权区间调度问题，具有复杂的时间 O（N日志（N））。

@j_random_hacker's answer, below, is, in fact, the known solution to the weighted interval scheduling problem, with a complexity in time of O(N log(N)).

推荐答案

下面是一个 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.)