最大覆盖不相交间隔

Question

假设你有k<=10^5个区间 [a_i, b_i] \in [1,10^18] （其中一些可能重叠），你需要选择一组相互不相交的区间，使得它们的并集最大。不是不相交间隔的最大数量，但并集必须覆盖最多。

无法尝试所有可能的子集 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]

[1,2], [2,6], [3,4], [5,7] 溶胶 [1,2]u[3,4]u[5,7]
[2,30], [25,39], [30,40] 太阳 [2,30]

Answer 1

似乎有一个 O(k * log(k)) 解决方案。可以用线段树数据结构来实现。

我们可能首先填充一些endPos段结尾数组，然后对其进行排序。记住每个段对应的endPos索引。为此，让 endPosIdx 成为 endPosIdx_j 将在 中存储索引的数组endPos 第 j 段结束。

接下来介绍线段树。它将处理以下请求：
1. getMax(i) - 获取 [0, i].
范围内的最大值 2. update(i, value) - 用 value.
更新第 i 个位置的最大值 i 是 endPos 数组中的索引。调用 getMax(i) 我们询问如果没有段在 endPos_i[= 之后结束，我们可以达到什么最大覆盖率66=]。调用 update(i, value) 我们说现在存在一个长度为 value 的覆盖，结束于 endPos_i.

按起始位置对所有段进行升序排序 a_j。按顺序处理它们。要点是如果我们一定要在结果集中取当前段，则找到最大的覆盖。当前覆盖将等于当前段的长度和结束于 before 当前段的最大覆盖的总和。令 j 为当前段的索引（它们按起始位置排序）。设 i 是 endPos_i ≤ a_j[= 的最大索引66=]（i可以通过二分查找从j中找到）。然后我们可以找到

覆盖_j = 长度_j + getMax(i)

接下来我们应该更新线段树调用update(endPosIdx_j, cover_j)并进行下一段。

处理所有段后，可以通过调用 getMax(size(endPos)).
找到解决方案

Answer 2

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

首先按区间上限（b_i）对区间进行排序。让 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
在满足 1+2

现在我们要计算 f(1), f(2), ..., f(k) 和 return 它们的最大值。显然，最优解对应于 f(i) 之一，因此最大 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

我们为 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)}，最优解

最大覆盖不相交间隔

Max coverage disjoint intervals

algorithm

intervals

greedy

cover