From: Bryan Richardson <btrichardson@...>
Date: 2008-08-07T03:48:58+09:00
Subject: Need help detecting overlapping ranges

Hello all,

I am writing some code where I create a bunch of ranges, then at the end
I want to create new ranges out of any ranges that overlap one another.
For example, say I have the following ranges:

(1..5) (7..11) (22..29) (5..8)

Given the ranges above, I want to end up with the following ranges:

(1..11) (22..29)

Here is the code I've come up with so far (ranges is an array of ranges
similar to what I described above in my example):

  ranges = @failed.outages
  changes = true
  while changes
    changes = false
    outages = ranges.collect { |range| range.to_a }
    ranges.clear
    while !outages.empty?
      outage = outages.shift
      outages.each do |n|
        unless (outage & n).empty?
          outage = (outage + n).uniq.sort
          outages.delete(n)
          changes = true
        end
      end
      ranges << (outage.first..outage.last)
    end
  end
  return ranges.sort { |a,b| a.first <=> b.first }

This code works, but it is *EXTREMELY* slow (my current array of ranges
is averaging out to ~24000 range elements).  Anyone have an idea of how
to speed it up?

--
Thanks!
Bryan
-- 
Posted via http://www.ruby-forum.com/.