在Ruby中测试重叠数组

Question

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

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

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

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

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

Answer 1

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

所以你的阵列变成了[100..300, 400..500].

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

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

现在要检查范围是否r与范围数组中的任何范围重叠,您只需要检查范围数组中的任何范围是否overlap?(r, r2)为真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