最大覆盖不相交间隔

假设您有 k

无法尝试所有可能的子集 2^k 不可行。 贪婪方法按 a_i （区间覆盖算法）排序，按 b_i （最大不相交区间数算法）排序不起作用 不知道是否有动态程序解决方案。 考虑到输入的大小，我认为解决方案应该是 O(k log k) 或 O(k)

例子 1. [1,4]、[3,5]、[5,9]、[7, 18] 溶胶[3,5]u[7,18]

2. [1,2]、[2,6]、[3,4]、[5,7] 溶胶 [1,2]u[3,4]u[5,7]

3. [2,30]、[25,39]、[30,40] 溶胶 [2,30]

问题可以解决O(k log(k)).

首先按区间的上限对区间进行排序（b_is). Let 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)是一个集合：

1. 包含区间I(i)
2. 不包含任何上限高于的区间b_i
3. 在满足 1+2 的（非重叠）间隔集合中具有最大覆盖范围

现在我们要计算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) for 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) is f(4)对应于间隔集合{I(1), I(4)}，最优解。