Testing for overlapping arrays in Ruby -

say have array of arrays in ruby,

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

that i'm building adding successive lines of csv data.

what's best way, when adding new subarray, test if range covered 2 numbers in subarray covered previous subarrays?

in other words, each subarray comprises linear range (100-300 , 400-500) in example above. if want exception thrown if tried add [499,501], example, array because there overlap, how best test this?

since subarrays supposed represent ranges, might idea use array of ranges instead of array of array.

so array becomes [100..300, 400..500].

for 2 ranges, can define method checks whether 2 ranges overlap:

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

now check whether range r overlaps range in array of ranges, need check whether overlap?(r, r2) true r2 in array of ranges:

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

which can used this:

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

here any_overlap? takes o(n) time. if use any_overlap? every time add range array, whole thing o(n**2).

however there's way want without checking each range:

you add ranges array without checking overlap. check whether range in array overlaps other. can efficiently in o(n log n) time sorting array on beginning of each range , testing whether 2 adjacent ranges overlap:

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