From: Dave Woodworth <user296@...>
Date: 2009-04-12T21:11:57+09:00
Subject: more efficient date range comparison

Hello all

I'm writing a calendar application that needs to check for conflicts
between recurring entries. Each Entry object has a recurrences() method
which returns an array of ranges - each range contains the start and end
times of each future occurence.

I need to check for conflicts between new and existing entries. I'm
doing this by checking that none of the future occurences of the new
entry clash with future occurences of existing entries:

def conflicts?(other)
  conflicts = 0
  recurrences.each do |my_rec|
    other.recurrences.each do |other_rec|
      start, finish = other_rec.first, other_rec.last
      conflicts += 1 if my_rec.include?(start) ||
my_rec.include?(finish)
    end
  end
  conflicts > 0
end

recurrences() defaults to returning all occurences between start time
and start time + 1 year

the problem is this method is not the most efficient in the world.
comparing just two entries, each with a daily recurrence over 1 year,
leads to 365 * 365 comparions (on my machine that takes 4+ seconds).
There may be any number of existing entries to compare a new entry to so
the method I have now is useless.

I don't have a computer science or maths background but I've been
reading various textbooks on algorithms and I havn't been able to find a
way to optimize the method. Does anyone else have any ideas?

thanks
Dave
-- 
Posted via http://www.ruby-forum.com/.