From: LAMBEAU Bernard <blambeau@...>
Date: 2009-04-13T16:36:23+09:00
Subject: Re: more efficient date range comparison

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

On Mon, Apr 13, 2009 at 9:21 AM, LAMBEAU Bernard <blambeau@gmail.com> wrote:
> Oops, you are perfectly right ... sorry!
>
> blambeau
>
> On Mon, Apr 13, 2009 at 9:16 AM, LAMBEAU Bernard <blambeau@gmail.com> wrote:
>> It's a OR, not a AND, so it seems correct ... no? Seems to be the
>> classical overlap operator on simple intervals.
>>
>> blambeau
>>
>> On Mon, Apr 13, 2009 at 8:57 AM, Albert Schlef <albertschlef@gmail.com> wrote:
>>> Dave Woodworth wrote:
>>>>       conflicts += 1 if my_rec.include?(start) ||
>>>> my_rec.include?(finish)
>>>
>>> Off topic: I think you have a bug here. If my_rec is, say, 20..40, and
>>> other_rec is, say, 10..50, your test won't detect this conflict (because
>>> neither 10 nor 50 are included in the my_rec range).
>>> --
>>> Posted via http://www.ruby-forum.com/.
>>>
>>>
>>
>>
>
>