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

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

Given a set of ranges:
(e.g. S = {(1, 4), (30, 40), (20, 91) ,(8, 10), (6, 7), (3, 9), (9, 12), (11, 14)}. And given a target range R (e.g. R = (3, 13) – meaning the range going from 3 to 13). Write an algorithm to find the smallest set of ranges that covers your target range. All of the ranges in the set must overlap in order to be considered as spanning the entire target range. (In this example, the answer would be {(3, 9), (9, 12), (11, 14)}.

解决这个问题的最佳方法是什么?我以为这将使用贪心算法完成.在上面的示例中,我们将查找与3相交的所有数字,并从具有最高最大值的数字中选择.然后我们会对刚刚选择的那个做同样的事情.所以,既然我们选择了(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,最大<问题是这仍然可能还不够.仍然存在在我们的范围范围内具有大量重复序列的潜在问题.如果我们的范围列表包含类似{(6,7),(6,7),(6,7),(6,7),(6,7)}的内容,我们每次都要查看它们,甚至虽然它们对我们没用.即使我们只是存储唯一值(通过将它们全部置于一组中),我们可能会有一个非常大的范围,一系列范围在我们的目标范围内,但我们内部也有一个范围几乎跨越整个目标范围. 什么是查询我们的范围的有效方法?或者可能,解决这个问题的更有效算法是什么?

如何使用间隔树进行查询? ( 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),因为我们已经知道(6,8)的小腿数较少,因此我们会向R的低点做更长的路径.所以你在我们去的时候消除间隔的想法是有道理的.可以这样的工作吗?

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
相关文章
相关标签/搜索