Hm, my alogorithm analysis is quite rusty but I believe you
would have to
get rid of m and replace it as an expression of n; reason
being that m is
part of the result and not part of the input. So you
probably have to
calculate something like an average number of range for the
set of input
range. Difficult without further knowledge of the data's
nature. My gut
guess is that for random numbers the number of ranges is
rather close to n
so that would make O(n*log n) which doesn't exactly look
better than O(n)...
true, this is optimized for the given case (m <= 2).
Anyway with the low numbers of n we're dealing with here
other effects are
likely more dramatic. So doing a benchmark of all solutions
provided might
yield surprising results.>> Btw, here's another funny idea:
>>
>> -----------------
>> data = [3, 4, 5, 6, 7, 8, 9, 15, 38, 39, 40, 41, 6789, 6790,
>> 9998, 9999]
>> ranges =
>>
>> data.inject(0) {|s,x| s | (1 << x)}.to_s(2).reverse!.scan(/1+/) do
>> >m> s = $`.length
>> ranges << (s .. (s + m.length - 1))
>> end
>>
>> puts ranges
>> -----------------
>>
>> Kind regards
>>
>> robert
>
> Rofl, indead a funny idea. For sure the slowest one mentioned hereDid you benchmark them?
this creates a BigInt 1250 Bytes width, alocates 10 kByte of memory,
fills it, reverses it, and scans it with a regular expression. All to
look at 17 fixnums, it may be O(C * n) but with a realy huge C.
> d = [1, 3, 4, 5, 6, 7, 8, 9, 15, 38, 39, 40, 41, 6789, 6790, 9998,
> 9999] puts
d.inject([d[0]..d[0]]){|r,x|r<<(((r.last.end+1>=x)?r.pop.end: x)..x)}
>
> lets see if you can beat this :))Nah, unlikely. ATM I don't feel like investing that much
time. Btw, two
points of your solution vs. the bit set approach (above):- This solution breaks for the empty array.
>> [0] .. [0]
ArgumentError: bad value for range
from (irb):5- It needs a sorted array.
So checks to cope with these make your bit a bit longer. :-}
ok, I don't want to invest that much time either, but your code
doesn't cope with negativ numbers 
it was fun,
Simon