From: "Kroeger Simon (ext)" <simon.kroeger.ext@...>
Date: 2005-08-05T23:34:51+09:00
Subject: Re: algorithm help

 
>      [5, 3, 0]

ok, this is sorted, but I thought it is sortet 
from smallest to largest. Reversing the array alone
has O(n) complexity.

>      harp:~ > cat a.rb
>      tests = [
>        [],
>        [0],
>        [0,1],
>
> [..snip..]
>
> it is short though ;-)

...but not made for reversed arrays. Here is a version
that has O(log n) complexity for all cases (even large
number of ranges) but is also made for sorted arrays 
(lowest to highest)

------------------------------------------------------
def toRanges d
    return d.size>0 ? [d.first..d.last]:[] if 
        (d.last - d.first)==d.size-1 || d.size==0
    r1, r2 = toRanges(d[0...(d.size/2)]), 
        toRanges(d[(d.size/2)..-1])
    r1.last.last+1>=r2.first.first ? r1[0..-2]+
        [r1.last.first..r2.first.last]+r2[1..-1]:r1+r2
end

puts toRanges((1..40).to_a + (123..789).to_a + 
    [6789, 6790, 9998, 9999] )

------------------------------------------------------

if you have to process reversed arrays the fastest way
would be to write another method for that case and call
only the right one based on (data.first > data.last).

greets

Simon