Say I have an array of arrays in Ruby,

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

that I'm building by adding successive lines of CSV data.

What's the best way, when adding a new subarray, to test if the range covered by the two numbers in the subarray is covered by any previous subarrays?

In other words, each subarray comprises a linear range (100-300 and 400-500) in the example above. If I want an exception to be thrown if I tried to add [499,501], for example, to the array because there would be overlap, how could I best test for this?

-------------Problems Reply------------

Since your subarrays are supposed to represent ranges, it might be a good idea to actually use an array of ranges instead of an array of array.

So your array becomes `[100..300, 400..500]`

.

For two ranges, we can easily define a method which checks whether two ranges overlap:

`def overlap?(r1, r2)`

r1.include?(r2.begin) || r2.include?(r1.begin)

end

Now to check whether a range `r`

overlaps with any range in your array of ranges, you just need to check whether `overlap?(r, r2)`

is true for any `r2`

in the array of ranges:

`def any_overlap?(r, ranges)`

ranges.any? do |r2|

overlap?(r, r2)

end

end

Which can be used like 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. So if you use `any_overlap?`

every time you add a range to the array, the whole thing will be `O(n**2)`

.

However there's a way to do what you want without checking each range:

You add all the ranges to the array without checking for overlap. Then you check whether any range in the array overlaps with any other. You can do this efficiently in `O(n log n)`

time by sorting the array on the beginning of each range and then testing whether two adjacent ranges overlap:

`def any_overlap?(ranges)`

ranges.sort_by(&:begin).each_cons(2).any? do |r1,r2|

overlap?(r1, r2)

end

end