测试用于Ruby的

Question

重叠阵列说我有阵列在红宝石阵列，

[[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