最大覆盖不相交区间

Question

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

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

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

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

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

- Moro Silverio

---

区间数量，a_i和b_i的值最多是多少？ - Ivan Gritsenko

您尝试过什么？ - Ivan Gritsenko

提示：您可以按左边界排序并计算 dp[i] = 以第 i 个段结束的最大联合。如果您正确跟踪事件（或使用类似于线段树的数据结构），则可以在 O(k log k) 时间内完成。 - kraskevich

Answer 1

问题可以通过 O(k log(k)) 的复杂度来解决。

首先按照区间的上限（b_i）对区间进行排序。设 I(1), I(2), ..., I(k) 为已排序的区间列表。

即，

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

将区间 I(i) 的长度表示为 w(i)。即，

w(i) = b_i - a_i

将I(i)作为最后一个区间，定义f(i)为最优解的总长度。也就是说，与f(i)相对应的解是一个集合，其中：

1. 包含区间I(i)
2. 不包含上界大于b_i的任何区间
3. 在满足1和2的非重叠区间集中具有最大覆盖范围

现在我们要计算f(1), f(2), ..., f(k)并返回它们中的最大值。显然，最优解对应于其中一个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)}，为最优解。

- snakile

---

谢谢。我使用了二分查找来找到 max{f(j) | b_j < a_i}。 - Moro Silverio

一切都很好，你的解释帮了我很多，我已经编写了代码并得到了通过。我可以在这里提交代码，这可能会帮助其他人在未来。 - Moro Silverio

我认为，它不是O(k log(k))，在最坏情况下找到max{f(j) | b_j < a_i}需要O(k)。 - Mukhtar Bimurat

@MukhtarBimurat：是的，但要知道您应该计算值f的顺序（您考虑间隔的顺序），我不知道如何在没有对它们进行排序的情况下完成它？ - a3nm

一个计算错误：f(3) = w(3) + max{f(1)} = 4 + 1 = 5 需要改为 4 + 3 = 7。 - perotom

如果你尝试第三个例子，它不起作用。f(i)不是最大值。你需要再次使用max来获得最佳解决方案。我有什么遗漏吗？ - perotom

Answer 2

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

我们可以首先填充一些线段结束点的endPos数组，对其进行排序。为每个对应线段的endPos索引进行记忆。为此，让endPosIdx成为这样一个数组，其中endPosIdx_j将存储第j个线段结束的endPos中的索引。

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

按照它们的起始位置 a_j 递增的顺序对所有段进行排序。按照这个顺序处理它们。要点是，如果我们一定会在结果集中取当前段，则找到最大的覆盖范围。当前覆盖将等于当前段长度和结束于当前段之前的段的最大覆盖的长度之和。设j为当前段的索引（它们按起始位置排序）。然后让i成为这样的最大索引，即endPos_i ≤ a_j（i可以通过二分查找从j中找到）。然后我们可以找到

cover_j = length_j + getMax(i)

接下来，我们应该调用update(endPosIdx_j, cover_j)更新段树并继续处理下一个段。

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

- Ivan Gritsenko