detecting conflicts in recurring events

Question

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 occurrence.

I need to check for conflicts between new and existing entries. I'm doing this by checking that none of the future occurrences of the new entry clash with future occurrences 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 occurrences between start time and start time + 1 year

the problem is this method is not very efficient. comparing just two entries, each with a daily recurrence over 1 year, leads to 365 * 365 comparisons (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 haven't been able to find a way to optimize the method. Does anyone else have any ideas?

thanks

Dave

Answer 1

First of all, you can improve this by just causing an early function-return:

def conflicts?(other)
  conflicts = 0
  recurrences.each do |my_rec|
    other.recurrences.each do |other_rec|
      start, finish = other_rec.first, other_rec.last
      return true if my_rec.include?(start) || my_rec.include?(finish)
    end
  end
  false
end

This will however not improve the average performance of your algorithm but will only cause one comparision if there is a conflict. The only option you got is to detect "simple" collisions early. So like

• Store the type of recurrence (weekly, daily, monthly) into the recurrence object.
• If both are daily recurrences, find the first day where the might be a potential conflict. Example: daily, a: January-July, b: May-October should only check May,1st for a time-conflict. If there doesn't happen one, you do not need to check for any other conflicts.
• Do the same for different constellations (week-week, day-week, day-year).
• Avoid to write day-week and week-day - week_day(x,y) is the same as day_week(y,x).
• If you don't find a matching method, you will have to use the method given above as a fallback.

As you can see the latter is much more work - AND the worst-case execution time might be the same (since it uses the original algorithm as a fallback). Worst-case might be caused by an "irregular" reccurence ("each day one hour later") for example.

Answer 2

A few ideas:

1. Use a data structure pointing from a calendrical date to a list of all entries on that date. Then look inside the list of entries for that date for conflicts.
2. Look at week-of-day - A recurring entry on a Monday will never collide with one on a Wednesday (subsumed by the first idea).
3. Use expiration dates - When checking for collisions, only check the dates fitting the entry which expires earlier. You may get some inspiration from the Sieve of Eratosthenes.

Answer 3

Assuming the recurrences are sortable, you can sort them in O(n*log(n), and only compare to neighboring events. Here's a start:

def conflicts?(other)
 conflicts = 0
 # Generate all recurrences and sort
 all_recurrences = recurrences + other.recurrences
 all_recurrences.sort!

 # Keep track of what immediate neighbors could be conflicting
 conflicting = []
 all_recurrences.each do |my_rec| 
     conflicting.each do |other_rec| do
       start, finish = other_rec.first, other_rec.last
       if my_rec.include?(start) || my_rec.include?(finish) then
          # TODO update conflicting array: add my_rec + other_rec if conflicting
          conflicts += 1
       else 
          # TODO remove other_rec if not conflicting
       end
     end
 end
 conflicts > 0
end