覆盖目标区间的最便宜区间数

Question

所以我偶然发现了这个问题，有人发来了 Discord gc（无关紧要），它看起来真的很有趣。 我们有一个特定的目标间隔（在这个例子中，[20, 80]），然后是一些其他的次要间隔 （在本例中为 [20, 45]、[30, 75]、[40, 80]、[60, 95] 和 [90, 100]）。每个次级间隔都有一个成本，如图所示（线旁边的数字是成本）。 我们的目标是用最便宜的次要间隔集覆盖目标间隔

例如区间[20, 100]可以通过选择有costs的区间以最小的cost覆盖 10 + 20 + 5 + 15 = 50。（选择成本为 30 的区间而不是成本为 20 的区间 也会达到预期的结果，但总成本更高。）

最好的方法是什么？

我尝试的第一件事是在 C++ 中开发一个贪婪算法，就像在网上对其他类似问题所展示的那样 但我在“最便宜”的部分发现了麻烦。我怎样才能确保我使用的是最便宜的区间/区间子集来替代最昂贵的区间？

Answer 1

假设目标区间是从s到e，g(x)表示覆盖从s到x的最小成本（即你想要的答案是g(e)）。

您可以考虑最小成本的子问题 f(y) 来覆盖从 s 到 y 的目标区间，附加约束是没有任何东西被覆盖到 y 之外（即必须有一个次级区间恰好在 y 结束）。

如果你有 f(y)，你可以通过计算所有 y >= e 的 f(y) 的最小值来计算 g(e)。

要计算出 f(y)，您需要考虑所有以 y 结尾的区间 (a,y)，并计算 a 范围内所有 x 的最小值（f(x)+区间成本 (a,y)）<=x

如前所述，这将是 O(n^2)，因为要计算 f(y) 的 n 个值，并且每个值都需要 O(n) 来计算。这可以通过使用更好的数据结构来构建最少的查询来加速。

Answer 2

按端点对次级区间进行排序，并丢弃那些不与目标区间重叠的。

现在，您将为所有次要端点构建一个数组。对于每个端点，您将有 (x,cost)，其中 x 是端点，成本是覆盖目标到该端点的最低成本。

对于每个间隔，（开始，结束），您可以轻松计算其入口（结束，成本），方法是将间隔成本添加到刚好超过其起点的成本中。您可以在目前已构建的数组上使用二进制搜索找到该成本。请注意，新成本可能会使您可以删除的数组末尾的某些结果无效。

二分搜索需要 O(log n) 时间，总成本为 O(n log n)，与初始区间排序相同。

如果你记得产生数组中每个成本的区间，那么你可以通过向后工作轻松地在 O(n) 时间内计算覆盖区间集。