在 Ruby 中测试重叠数组

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

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

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

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

换句话说，在上面的示例中，每个子阵列都包含线性范围（100-300 和 400-500）。例如，如果我尝试将 [499,501] 添加到数组中，因为会出现重叠，因此希望抛出异常，那么我该如何最好地对此进行测试？

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

所以你的数组变成[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

Here any_overlap? takes 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