覆盖区间的并

Question

我试图实现一个问题的解决方案，这个问题归结为区间覆盖。通过搜索，我知道这通常是用贪婪的方法解决的，但我自己的第一个想法是使用广度优先搜索。我开始假设区间的联合是一个区间，并且所有的间隔都是封闭的。问题是：

给定k个闭区间的

找到一个元素尽可能少的子集，使得从原始集合到一个区间中的每个点都在找到的子集中的一个区间内。

我的想法是在图中工作，其中区间是顶点，如果对应的区间重叠，两个顶点就形成一个无向边。在特殊情况下，当联合是一个区间时，我可以选择包含端点和起始点的节点，具有最大长度的节点，而最小长度之间的路径是最优解。我的问题是:如何有效地构建区间图，从而避免查看每一对间隔。我尝试过不同的方法来对间隔进行排序，但我似乎仍然没有摆脱二次时间。

Answer 1

我认为在最坏的情况下，你无法摆脱二次时间。这是因为边的数目可能是二次的。

但是这里不需要普通的最短路径算法(比如Dijkstra)。从第一个间隔开始(起点最低的那个)。然后选择一个间隔，在这个间隔之后开始，其结束是最高的。重复直到你到达终点。

Answer 2

我之所以回答这个问题，是因为据我所知，以前的条目没有正确回答，或者是不完整的。

有一个在O(N log N)上运行的算法，其中N是闭段的数目：

1. 按左端对段进行升序，通过优先处理最大右端的部分(断开联系并不重要)，
2. 采用了从“左到右”的贪婪策略：

2.1虽然不漏点，但强制选择左端最大的段

2.2如果有遗漏点，就没有解决办法。

2.3否则，转到2.1

步骤1的时间复杂度为O(N log N)，步骤2的时间复杂度为O(N)。因此，这种贪婪的算法花费了O( N )时间。

希望这能有所帮助！