On Sat, Apr 24, 2010 at 7:37 PM, steve ross <cwdinfo / gmail.com> wrote:
> On Apr 24, 2010, at 1:16 AM, Robert Dober wrote:
>>
>> On Sat, Apr 24, 2010 at 2:08 AM, steve ross <cwdinfo / gmail.com> wrote:
>>> The algorithm I proposed for overlaps? is (by my count) at worst O(2). This one looks like at least O(n*m). Maybe I'm wrong about that. In any case, a good puzzle.
>> Ah indeed that was the point I did not understand, it did not seem to
>> work for all cases. The arrays contain ranges which are not
>> contiguous. OP's algorithm does not work either, but you correctly
>> translated it into an O(1).
>> [ O(2) is a funny way to say it BTW, but I got the picture ;). ]
>>
>> Cheers
>> R.
>
> I missed the discontiguous part of the problem and focused on the overlap. Still, the same approach works, as time spans are, by definition ordered.heck the lower boundary, the upper boundary, then and only then do you check any intermediate ranges. Again, it's an interesting problem, but if there are numerous tests it can be incredibly time consuming because of the number of comparisons. The pruning I suggest keeps these comparisons to a minimum. Probably premature optimization, but I happen to know this one :)
>

no I am sorry, look at this example a=[1..2,9..10], b=[ 3..4] if it
were not for this I would write it in O(1) too, it is readable enough
and expanding the ranges looks bad (I know I did that ;).
So finally I like this
def overlaps a, b
  a.any?{ |ar| b.any?{ |br| <<your code here>> } }
end
although O(n*m) it will probably quite fast for reasonable values for
n and m as we loop over the ranges and not the expanded ranges now. :)
(and use the fast kernel Enumerable methods)

As a side note I am quite surprised that there is no
Enumerable#overlaps? or #distinct?.

Cheers
R.

-- 
The best way to predict the future is to invent it.
-- Alan Kay