From: "David A. Black" <dblack@...>
Date: 2008-08-07T07:06:06+09:00
Subject: Re: Need help detecting overlapping ranges

Hi --

On Thu, 7 Aug 2008, Bryan Richardson wrote:

> Thanks to all who replied!  I took the main advice of all of your posts
> to be "don't convert ranges to arrays stupid!!!" and also "don't do this
> recursively stupid!".  :)
>
> With that in mind, here's what I came up with (I didn't want to just
> copy someone's code... I don't learn anything that way!) -- it seems to
> be much faster:
>
> def merge_outages
>  ranges = @failed.outages.sort { |a,b| a.first <=> b.first }
>  outages = Array.new
>  while !ranges.empty?
>    range = ranges.shift
>    loop do
>      if ranges.empty?
>        break
>      else
>        if (range.last + 1) >= ranges.first.first
>          range = (range.first..ranges.first.last)
>          ranges.shift
>        else
>          break
>        end
>      end
>    end
>    outages << range
>  end
>  return outages
> end

I did something similar in trying to implement Martin's algorithm. I
haven't tested it beyond eyeballing the results for this one run:

ranges = [(1..5), (7..11), (22..29), (5..8)].sort_by {|r| r.first }
outages = [ranges.shift]

ranges.each do |r|
   if outages[-1].include?(r.first)
     outages[-1] = Range.new(outages[-1].first, r.last)
   else
     outages.push(r)
   end
end

p outages


David

-- 
Rails training from David A. Black and Ruby Power and Light:
  *  Advancing With Rails    August 18-21    Edison, NJ
  * Co-taught by D.A. Black and Erik Kastner
See http://www.rubypal.com for details and updates!