最大覆盖脱节间隔 [英] Max coverage disjoint intervals

问题描述

假定您在[1,10 ^ 18]中有k <= 10 ^ 5个间隔[a_i，b_i]（（其中一些可能重叠），并且需要选择一组相互不相交的间隔，以使它们联合是最大的。不是最大的不相交间隔数，但联合必须涵盖最多的间隔。

Assume you have k<=10^5 intervals [a_i, b_i] \in [1,10^18] (some of them may overlap), and you need to choose a set of intervals mutually disjoint such that their union is maximal. Not maximum number of disjoint intervals, but the union must cover the most.

无法尝试所有可能的2 ^ k个子集不可行。
贪婪方法无法通过a_i（间隔覆盖算法）进行排序，而无法通过b_i（不连续间隔算法的最大数目）进行排序
无法确定是否存在动态程序解决方案。
鉴于输入的大小，我认为解决方案应为O（k log k）或O（k）

Can't try all possible subsets 2^k infeasible. Greedy approaches ordering by a_i ( interval covering algorithm) and ordering by b_i ( maximum number of disjoint intervals algorithm ) didn't work Can't figure out if there is a dynamic program solution. Given the size of the input, I think the solution should be O(k log k) or O(k)

示例
1。 [1,4]，[3,5]，[5,9]，[7，18]
Sol [3,5] u [7,18]

Examples 1. [1,4], [3,5], [5,9], [7, 18] Sol [3,5]u[7,18]

1. [1,2]，[2,6]，[3,4]，[5,7]
   Sol [1， 2] u [3,4] u [5,7]

1. [1,2], [2,6], [3,4], [5,7] Sol [1,2]u[3,4]u[5,7]

[2,30]，[25,39]，[30,40]
Sol [2,30]

[2,30], [25,39], [30,40] Sol [2,30]

推荐答案

问题可能是在 O（k log（k））中求解。

首先按区间上限对区间进行排序（ code> b_i s）。设 I（1），I（2），...，I（k）为排序间隔的列表。也就是说，

First sort the intervals by their upper bounds (the b_is). Let I(1), I(2), ..., I(k) be the list of sorted intervals. That is,

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

用 w（i）表示间隔时间 I（i）。也就是说，

Denote by w(i) the length of interval I(i). That is,

w(i) = b_i - a_i

用 f（i）表示最后间隔为<$ c $的最优解的总长度c> I（i）。也就是说，对应于 f（i）的解决方案是一个集合，其中：

Denote by f(i) the total length of the optimal solution among those whose last interval is I(i). That is, the solution corresponding to f(i) is a set which:

1. 包含间隔 I（i）


2. 不包含上限大于 b_i的任何间隔


3. 在满足（1 + 2）个（非重叠）区间的集合中具有最大覆盖率

现在我们将计算 f（1），f（2），...，f（k）并返回最大值他们所有人的价值。显然，最佳解对应于 f（i） s之一，因此最大 f（i）为

Now we are going to compute f(1), f(2), ..., f(k) and return the maximum value of them all. Clearly, the optimal solution corresponds to one of the f(i)s and therefore the maximal f(i) is the optimal solution.

要计算每个 f（i），我们使用动态编程。我们通过依赖以下递归关系来做到这一点：

To compute each f(i) we use dynamic programming. We do this by relying on the following recurrence relation:

f(i) = w(i) + max{f(j) | b_j < a_i}

我将用您的第一个输入示例演示计算：

I'll demonstrate the computation with your first input example:

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

我们为<$ c $计算 f（i） c> i = 1，2，3，4 ：

We compute 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）是 f（4），它对应于间隔 {I（1），I（4）} ，最优解。

The maximum f(i) is f(4) which corresponds to the set of intervals {I(1), I(4)}, the optimal solution.

这篇关于最大覆盖脱节间隔的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！