Prev: If-Else within a loop going through array elements...
Next: Burn Audio CD
From: Ed Howland on 24 Apr 2010 15:52
I'd check out "runt" ]1\ Ruby temporal expressions. I've used these
before in a scheduling application to detect scheduling conflicts (two
meetings and attendees availably if they overlap - which seems to be
what you are checking).

Runt allows for English-like expressions

nine_to_ten = REDay.new 9,00,10,00
eighjt_to_eleven = REDay.new 8,00,11,00

mon = DIWeek.new Mon
wef = DIWeek.new Wed

mon_8_11 = mon & eight_to_eleven
wed_9_10 = wed & nine_to_eleven

These are based on Martin Fowler's Temporal Expressions.

[1] http://runt.rubyforge.org/

Cheers,
Ed

Ed Howland
http://greenprogrammer.wordpress.com
http://twitter.com/ed_howland



On Sat, Apr 24, 2010 at 2:12 PM, Robert Dober <robert.dober(a)gmail.com> wrote:
> On Sat, Apr 24, 2010 at 7:37 PM, steve ross <cwdinfo(a)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(a)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 Check 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
>
>

First  |  Prev  | 
Pages: 1 2 3
Prev: If-Else within a loop going through array elements...
Next: Burn Audio CD