× {{alert.msg}} Never ask again
Get notified about new tutorials RECEIVE NEW TUTORIALS

Detecting overlapping ranges in Ruby

Simone Carletti
Mar 21, 2015
<p>This is a very interesting puzzle, especially if you care about performances. </p> <p>If the ranges are just two, it's a fairly simple algorithm, which is also covered in <a href="http://api.rubyonrails.org/classes/Range.html#method-i-overlaps-3F"><code>ActiveSupport</code> <code>overlaps?</code></a> extension.</p> <pre><code>def ranges_overlap?(r1, r2) r1.cover?(r2.first) || r2.cover?(r1.first) end </code></pre> <p>If you want to compare multiple ranges, it's a fairly interesting algorithm exercise. </p> <p>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.</p> <p>A more efficient solution is to <a href="http://www.perlmonks.org/?node_id=841368">order the ranges</a> and execute a binary search, or to use data structures (such as trees) to make possible to compute the overlapping.</p> <p>This problem is also explained in the <a href="http://en.wikipedia.org/wiki/Interval_tree#Intersecting">Interval tree</a> page. Computing an overlap essentially consists of finding the intersection of the trees.</p> <p>This tip was originally posted on <a href="http://stackoverflow.com/questions/28030931/Detecting%20overlapping%20ranges%20in%20Ruby/28031120">Stack Overflow</a>.</p>
comments powered by Disqus