detecting recurring appointment conflicts

[Ben Chobot <bench@xxxxxxxxxxxxxxx>]

I'd like to store recurring appointments in my database, and be pretty  
accepting in the scheduling of those appointments. For instance, I  
want to accept both "every other Tuesday starting 2008-11-04" as well  
as "every 3rd October 13th starting 2009." Storing those appointments  
isn't that hard, but what isn't at all obvious to me (and what I'm  
hoping is obvious to somebody else) is how to efficiently detect if  
and when overlaps will occur.

I can see a few ways to look for schedule overlaps in a defined  
window, but ideally, I'd like to know if there will be overlaps at any  
time, not just in, say, the next 10 years. (Though, admittedly, the  
next 10 years is probably sufficient.) Is this something somebody has  
tackled before?