最大覆盖不相交间隔

Question

[2,30],[25,39],[30,40]溶胶[2,30]

Answer 1

这个问题可以在O(k log(k))中解决。

首先，按照区间的上界(b_is)对其进行排序。设I(1)，I(2)，...，I(k)为排序间隔的列表。也就是，

b_1 <= b_2 <= ... <= b_k

用w(i)表示间隔的长度i(i)。也就是，

w(i) = b_i - a_i

null

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

对于i=1,2,3,4，我们计算F(i):

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)}，最优解。