From: Stefan Lang <perfectly.normal.hacker@...>
Date: 2008-08-07T05:40:15+09:00
Subject: Re: Need help detecting overlapping ranges

2008/8/6 Bryan Richardson <btrichardson@gmail.com>:
> 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?

I guess it's slow because it's doing many Range to Array conversions.
Here's a version that does no such conversions:

    # Assumption: for every range: range.end >= range.begin
    def overlap(ranges)
      ranges = ranges.dup
      new_ranges = []
      until ranges.empty?
        cur = ranges.pop
        overlap = ranges.find { |range|
          cur.member?(range.begin) || cur.member?(range.end) ||
            range.member?(cur.begin) || range.member?(cur.end)
        }
        if overlap
          new_begin = cur.begin < overlap.begin ? cur.begin : overlap.begin
          new_end = cur.end > overlap.end ? cur.end : overlap.end
          join = Range.new(new_begin, new_end)
          ranges.map! { |range| range.equal?(overlap) ? join : range }
        else
          new_ranges << cur
        end
      end
      new_ranges
    end

(And in case Gmail messes up the formating:
http://pastecode.com/?show=m69851851)

So I've tried it only with the one example you've given and
I didn't actually benchmark it.

Stefan