測試用於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