Detecting overlapping ranges in Ruby

Question

I have array of ranges :

[[39600..82800], [39600..70200],[70200..80480]]

I need to determine if there is overlapping or not.What is an easy way to do it in ruby?

In the above case the output should be 'Overlapping'.

Answer 1

This is a very interesting puzzle, especially if you care about performances.

If the ranges are just two, it's a fairly simple algorithm, which is also covered in ActiveSupport overlaps? extension.

def ranges_overlap?(r1, r2)
  r1.cover?(r2.first) || r2.cover?(r1.first)
end

If you want to compare multiple ranges, it's a fairly interesting algorithm exercise.

You could loop over all the ranges, but you will need to compare each range with all the other possibilities, but this is an algorithm with exponential cost.

A more efficient solution is to order the ranges and execute a binary search, or to use data structures (such as trees) to make possible to compute the overlapping.

This problem is also explained in the Interval tree page. Computing an overlap essentially consists of finding the intersection of the trees.