在Ruby中测试重叠数组

假设我在Ruby中有一个数组数组，

[[100,300], [400,500]] 

我正在通过添加连续的CSV数据行来构建。

添加新子arrays时，最好的方法是测试子arrays中两个数字所覆盖的范围是否被任何先前的子arrays覆盖？

换句话说，每个子arrays在上面的示例中包括线性范围（100-300和400-500）。 如果我想要例如将[499,501]添加到数组中，因为会有重叠，我想要抛出exception，我怎么能最好地测试呢？

Answer 1

由于您的子数组应该表示范围，因此实际使用范围数组而不是数组数组可能是个好主意。

所以你的arrays变成[100..300, 400..500] 。

对于两个范围，我们可以轻松定义一个检查两个范围是否重叠的方法：

 def overlap?(r1, r2) r1.include?(r2.begin) || r2.include?(r1.begin) end 

现在要检查范围r是否与范围数组中的任何范围重叠，您只需检查范围数组中的任何r2是否overlap?(r, r2)为真：

 def any_overlap?(r, ranges) ranges.any? do |r2| overlap?(r, r2) end end 

哪个可以这样使用：

 any_overlap?(499..501, [100..300, 400..500]) #=> true any_overlap?(599..601, [100..300, 400..500]) #=> false 

在这里any_overlap? 花费O(n)时间。 那么如果你使用any_overlap? 每次向数组添加一个范围时，整个事件都是O(n**2) 。

但是，有一种方法可以在不检查每个范围的情况下执行您想要的操作：

将所有范围添加到数组而不检查重叠。 然后检查数组中的任何范围是否与任何其他范围重叠。 您可以在O(n log n)时间内有效地执行此操作，方法是在每个范围的开头对数组进行排序，然后测试两个相邻范围是否重叠：

 def any_overlap?(ranges) ranges.sort_by(&:begin).each_cons(2).any? do |r1,r2| overlap?(r1, r2) end end