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 wrote:> On Sat, Apr 24, 2010 at 7:37 PM, steve ross wrote: >> On Apr 24, 2010, at 1:16 AM, Robert Dober wrote: >>> >>> On Sat, Apr 24, 2010 at 2:08 AM, steve ross 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| <> } } > 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