From: Dave Woodworth <user296@...>
Date: 2009-04-16T20:54:05+09:00
Subject: Re: more efficient date range comparison

LAMBEAU Bernard wrote:
> Extracted from the CRUC project I mentionned (see the intersection
> method). I think the code below should make the job. Even if your
> range lists are not initially sorted, this algorithm should be better
> than the initial one: O(nlogn+mlogm+n+m) in the worst case.
> 
> # Assume you have two lists of ranges, each one being sorted by start 
> point
> my_ranges, other_ranges = ...
> 
> # Take the first two, as well as their extremities
> r1, r2 = my_ranges.shift, other_ranges.shift
> b1, e1 = r1.begin, r1.end
> b2, e2 = r2.begin, r2.end
> 
> until (my_ranges.empty? or other_ranges.empty?)
>   if e1<b2
>     # my end is before its begin, we don't overlap
>     r1 = my_points.shift
>     b1, e1 = r1.begin, r1.end
>   elsif
>     # its end is before my begin, we don't overlap
>     r2 = other_points.shift
>     b2, e2 = r2.begin, r2.end
>   else
>     # intersection found, it's a conflict
>     return true
>   end
> end
> 
> # All ranges are disjoint, no conflict
> return false
> 
> 
> 
> blambeau

thanks for your suggestions. I'm using a slightly modified version of 
the code you posted and it's about 8x faster. I'm sure it could be 
optimized further but it's good enough for now. thanks again!

dave
-- 
Posted via http://www.ruby-forum.com/.