假设你的K <= 10 ^ 5间隔[A_I，b_i] \在[1,10 ^ 18]（它们中的一些可能重叠），并且需要选择一个设定的时间间隔相互分离，使得他们的结合是最大的。 不相交的区间不是最大的数，但工会必须覆盖最。
不能尝试所有可能的子集2-1K-不可行。 贪婪的方法排序由A_I（区间覆盖算法）和b_i（不相交的区间算法的最大数）排序没有工作无法弄清楚是否有一个动态程序的解决方案。 由于输入的大小，我觉得解决方案应该为O（K数K）或O（K）
实施例1. [1,4]，[3,5]，[5,9]，[7,18]溶胶[3,5] U [7,18]
[1,2]，[2,6]，[3,4]，[5,7]溶胶[1.2]至[3.4]至[5.7]
[2,30]，[25,39]，[30,40]盐[2.30]
这个问题可以在解决O(k log(k))
首先通过他们的上限区间（排序b_i S）。 让I(1), I(2), ..., I(k)排序间隔的列表。 那是，
b_1 <= b_2 <= ... <= b_k
由表示w(i)的时间间隔的长度I(i) 那是，
w(i) = b_i - a_i
由表示f(i)的最优解的那些最后间隔之间的总长度I(i) 即，对应于该溶液f(i)是一组：
I(i) b_i 现在，我们要计算f(1), f(2), ..., f(k)并返回他们所有的最大值。 显然，最佳解决方案对应于所述的一个f(i) S和因此最大f(i)是最佳的解决方案。
为了计算每个f(i)我们使用动态规划。 我们依靠下面的递推关系做到这一点：
f(i) = w(i) + max{f(j) | b_j < a_i}
我会证明你的第一个输入例如计算：
I(1)=[1, 4], w(1)=3
I(2)=[3, 5], w(2)=2
I(3)=[5, 9], w(3)=4
I(4)=[7, 18], w(4)=11
我们计算f(i)为i=1, 2, 3, 4 ：
f(1) = w(1) + max{None} = 3
f(1) intervals: {I(1)}
f(2) = w(2) + max{None} = 2
f(2) intervals: {I(2)}
f(3) = w(3) + max{f(1)} = 4 + 1 = 5
f(3) intervals = {I(1), I(3)}
f(4) = w(4) + max{f(1), f(2)} = 11 + f(1) = 11 + 3 = 14
f(4) intervals = {I(1), I(4)}
最大f(i)是f(4)其对应于所述设定的时间间隔的{I(1), I(4)}中，最佳的解决方案。
这里似乎是一个O（K *日志（k））的解决方案。 它可以用线段树的数据结构来实现。
我们可以在第一填充某些endPos段结尾的数组排序。 记住每个对应endPos索引段。 对于这让endPosIdx是这样数组endPosIdxĴ将存储在所述第j个区段末端endPos的索引。
接下来我们将介绍一个段树。 这将处理以下要求：
1. getMax(i) -获得的范围内的最大值[0, i]
2. update(i, value) -更新最大值在i个与位置value 。
i是与endPos数组索引。 调用GetMax的（我），我们要求我们能达到什么最大的封面，如果段的非endPos 我后结束。 调用update（I，价值），我们说，现在存在一个长度值在endPos 我结束了盖子。
在由起始位置j增加顺序排序的所有段。 处理它们的顺序。 其要旨在于，找到最大的封面，如果我们肯定会利用当前段结果集。 当前盖将相等于当前段和电流之前结束段的最大盖的长度的总和。 令j当前段（它们被启动POS排序）的索引。 那么，让我是endPos 我 ≤第j这样的最大索引（i可从j由二进制搜索找到）。 然后，我们可以发现
盖J =长度为j + GetMax的（ⅰ）
下一步，我们应该更新段树调用update（endPosIdxĴ，盖j）的 ，并继续到下一段。
所有段的处理后的溶液可通过调用GetMax的（大小（endPos））中找到。
