找到一个区间的最小覆盖子区间数目

Question

假设我有一个区间(a,b)，以及一些子区间{(a_i,b_i)}_i，它们的并集是整个(a,b)。是否有一种有效的方法来选择一个最小基数子集，使其仍然覆盖(a,b)？

- Alex Coventry

---

你是在寻找最小数量的子区间，还是子区间集合中元素最少（因此重复最少）的那个？ - Bill the Lizard

Answer 1

从a或b开始的贪心算法总是给出最优解。

证明：考虑覆盖a的所有子区间集合S_a，显然，其中一个必须属于最优解。如果我们用S_a中右端点b_max最大（到达最右侧）的子区间(a_max,b_max)替换它，剩余的未覆盖区间(b_max,b)将是剩余区间的子集，并且可以用不多于最优解中类似未覆盖区间的子区间进行覆盖。因此，由(a_max,b_max)和剩余区间(b_max,b)的最优解构建的解也是最优的。

因此，只需从a开始，迭代选择最右侧的区间（并覆盖前一个区间的末端），重复直到达到b。如果将区间存储在增强区间树中，则我相信可以以log(n)的时间复杂度来选择下一个区间。

- Rafał Dowgird

---

你能详细说明一下：“剩余未覆盖的区间（bmax，b）将是最优解剩余区间的子集”吗？ - jfs

@JFS：假设最优解始于一个区间(ai,bi)，该区间覆盖了(a,bi)，并且留下了未覆盖的(bi,b)。从(amax,bmax)的定义中，我们知道bmax>=bi，因此(bmax,b)是(bi,b)的子集（子区间）。 - Rafał Dowgird

如果我们用Sa中的子区间(amax，bmax)替换它...：你是指子区间(amin，bmax)吗？而且我对(bmax，b)也不太确定。 - user183037

@user183037 'max'只是整个区间的索引。区间'foo'为(a_foo,b_foo)。(b_max,b)是剩余的区间。 - Rafał Dowgird

Answer 2

听起来像是动态规划。

以下是该算法的示例（假设区间已按结束时间排序并存储在列表中）：

//works backwards from the end
int minCard(int current, int must_end_after)
{
    if (current < 0)
        if (must_end_after == 0)
            return 0; //no more intervals needed
        else
            return infinity; //doesn't cover (a,b)
        
    if (intervals[current].end < must_end_after)
        return infinity; //doesn't cover (a,b)
   
    return min( 1 + minCard(current - 1, intervals[current].start),
                    minCard(current - 1, must_end_after) );
    //include current interval or not?
}

但它也应该涉及缓存（记忆化）。

- Artelius

---

"minCard()" 旨在获取最小基数，但问题要求一个具有最小基数的子集。 - jfs

这只是该算法的扩展，它还会跟踪用于形成最优值的子集。 - Artelius

@Artelius，你的算法复杂度是多少？ - Sumeet_Jain

最坏情况下的复杂度为O(n^2)。例如，当所有区间具有相同的结束点但不同的起始点时，所有这些起始点都将向后传播到开头。贪心算法更好。 - Artelius

Answer 3

有两种情况需要考虑：
情况1：在一个间隔结束后，没有重叠的间隔。在这种情况下，选择下一个起始时间最小且完成时间最长的间隔（amin，bmax）。
情况2：有1个或多个间隔与您正在查看的最后一个间隔重叠。在这种情况下，起始时间并不重要，因为您已经覆盖了它。 因此，优化完成时间。（a，bmax）。

情况1始终将第一个间隔选择为最佳集合中的第一个间隔（证明与@RafalDowgrid提供的相同）。

- user183037

---

问题中哪里出现了“时间”这个令人生畏的问题？ - greybeard

Answer 4

你的意思是子间隔仍然重叠，以便(a,b)在所有点上仍然完全被覆盖吗？

也许可以将子间隔本身分成基本块，与它们来自哪里相关联，这样您就可以为每个基本块间隔列出选项，考虑到子间隔还覆盖了其他区域。然后您可以使用基于每个子子间隔的搜索，并确保没有留下任何空隙。
然后需要高效地进行搜索...这会更加困难。

可以消除完全被其他更少数量的一组集合完全覆盖的任何间隔集合，并在预处理之后解决问题。
整体的最小值不是至少有一半的最小值吗？我不确定。

发现了一个链接到期刊的网站，但是无法阅读。:(

这将是一个 hitting set问题，一般情况下是NP_hard的。 对于this也无法阅读，但看起来是相反类型的问题。 无法阅读它，但另一个link提到了分割区间的方法。 这里有一份关于几何优化问题的随机算法的参考资料。 这个pdf的第35页有一个贪婪算法。 Karp (1972)的第11页提到了hitting-set，并被引用很多次。 谷歌result。研究很有趣，但我现在得走了。

- waynecolvin