给定一组范围S和重叠范围R,找到S中包含R的最小子集

Question

以下是某人给我的练习面试问题,我不确定最佳解决方案是什么:

给定一组范围:
(例如S = {(1, 4), (30, 40), (20, 91) ,(8, 10), (6, 7), (3, 9), (9, 12), (11, 14)},并给予目标范围R(例如R = (3, 13)-这意味着会从3到13的范围内)写一个算法来找到最小的范围集合覆盖你的目标范围内的所有在该范围内的. set必须重叠才能被视为跨越整个目标范围.(在这个例子中,答案是{(3, 9), (9, 12), (11, 14)}.

解决这个问题的最佳方法是什么？我以为这将使用贪婪算法完成.在上面的示例中,我们将查找与3相交的所有数字,并从具有最高max的数字中选择.然后我们会用我们刚刚选择的那个做同样的事情.所以,既然我们选择了(3,9),我们现在想要找到所有与9相交的范围,其中我们选择具有最高最大值的范围.在那次迭代中,我们选择了(9,12).我们对那个做同样的事情,我们发现与12相交的下一个范围,最高的最大值是(11,14).

在那次迭代之后,我们看到14大于13(我们的范围的最大值),所以我们可以停下来.

我对这个算法的问题是,如何有效地查询相交的范围？如果我们尝试线性搜索,我们最终会得到一个算法O(n^2).我的下一个想法是每次运行循环时从我们的列表中删除任何相交的范围.所以在第一次迭代中,我们交叉(1,4)和(3,9).在我们的下一次迭代中,我们交叉(9,12),(3,9)和(8,10).所以在最后一次迭代中,我们所要看的只有{(30,40),(20,91),(6,7)}.我们可以通过删除min> 13和max <3的所有内容来提高效率.问题是这仍然可能还不够.在我们的范围范围内存在大量重复序列的潜在问题.如果我们的范围列表中包含类似{(6,7),(6,7),(6,7),(6,7),(6,7)},我们将不得不通过这些每次都看,甚至虽然它们对我们没用.即使我们只存储唯一值(通过把它们放在一个集),我们可能有一个非常大的范围内,有一堆,这是我们的目标范围内的范围,但我们也有一个范围内,跨越几乎整个目标范围.

什么是查询我们的范围的有效方法？或者可能,解决这个问题的更有效算法是什么？

Answer 1

使用区间树进行查询怎么样？（https://en.m.wikipedia.org/wiki/Interval_tree）我不确定贪婪是否可以在这里工作。如果我们查看与 中的高点重叠的最后一组选择R，则每个选项的早期选择之间可能存在重叠，例如：

R = (2,10) and we have (8,10) and (7,10) both overlapping with (6,8)

在这种情况下，我们只需要存储一个值作为(6,8)路径的第二段；(6,8)当我们向低点走更长的路径时再次访问R将是多余的，因为我们已经知道(6,8)访问的航段数较少。所以你消除间歇的想法是有道理的。像这样的东西可以工作吗？

leg = 1
start with the possible end (or beginning) intervals
label these intervals with leg
until end of path is reached:
  remove the intervals labeled leg from the tree
  for each of those intervals labeled leg:
    list overlapping intervals in the chosen direction
  leg = leg + 1
  label the listed overlapping intervals with leg