Sunday, April 22, 2012

Detecting Date Range Conflicts

I'm working on an application for which one of the requirements is to not allow double-booking of rooms. Events in the system each have a start and end date and time, and when a new event is saved the system needs to tell the user if there are any overlaps with existing events in the same room.

This seems simple enough on the face of it but once I started thinking about all the possibilities around this I realized it was a lot more complex than I had initially thought. After some good old-fashioned "sledge hammer approach to get it working and to help gain understanding that will hopefully lead to eventual refinement" I think I have it licked.

I'm sure this is one of those classic problems that I just haven't had to deal with before which are always fun to think through, and whenever I run into one of these I resist the urge to search for a solution until I've wrapped my head around the problem and am ready to admit defeat. (And I really try never to admit defeat unless time constraints force me to.)

My first phase on solving this problem was to consider all the possible conflict states, which in plain english are:
  1. Since an event is assumed to have a non-zero duration, if either the start date/time or end date/time is exactly the same as the start date/time or end date/time of another event in the same room, that indicates a conflict. Note that one event's start date/time can be the same as another event's end date/time.
  2. If an event has a start date/time that is between the start and end date/time of another event, that indicates a conflict.
  3. If an event has an end date/time that is between the start and end date/time of another event, that indicates a conflict.
  4. If an event's start date/time is after that of another event but its end date/time is before that of another event, that indicates a conflict.
Granted some of these overlap, are redundant, or are the inverse of one another, but it was helpful as a first pass to simply think through all the scenarios to start forming a picture in my head of the various possibilities.

I'll spare you the messy middle step here and just say I then started coding all these scenarios (and anything else I thought of) and as I went through that exercise, I realized that this all boils down to some pretty simple logic.

Assume that we have two events and each one has a start and end date/time. We'll use start1 and end1 for the first event's dates, and start2 and end2 for the second event's dates. Here's what I came up with after a lot of head banging that I believe handles all the scenarios:

Consider yourself lucky I spared you the big hairy mess I had before I arrived at that solution. I believe that covers all the bases, however, and at least in the testing I did it certainly seems to.

The only other wrinkle in the case of this system is making sure that an event itself isn't detected as a conflict if someone updates the event and either doesn't change the dates or changes the dates in such a way that it would be considered a conflict with that event's state that's already in the database. To handle that case I still run the function to detect conflicts but if I only get back 1 and the ID is the same as the one I'm trying to save, I ignore it.

So that's how I spent more time than I care to admit this weekend. I'm curious if other people have solved this differently, and definitely would love to hear if this won't address some scenario I didn't consider.


Dennis Clark said...

Nice work on using mathematics to refactor your logical condition! Too often I see the "sledge hammer approach" applied to code logic where the logic ends up being more complex than it needs to be, creating a headache for future developers.

Your example reminds me of a refactoring/fix I did a couple of months back on a SQL query. The original query was over 20 lines long, and after applying some relational logic rules I fixed the bug and reduced the query to a far more readable 8 lines. It took more time than I wanted to spend on it, but I figured that I was paying off some technical debt in the process. I intend to post something about it in my Copious Free Time™.

One thing to consider in your example is that its correctness will probably not be obvious to many programmers, no matter how well you document it. Unit tests are extremely valuable in such cases: even if a developer isn't sure about how the code works, having a test suite that covers the normal and edge cases should be enough to convince them that it does indeed work. The unit tests can also serve to catch regressions in case a developer unwittingly makes a change that breaks the logic.

Matt Woodward said...

Very good point on the unit testing Dennis. I more or less did that with the testing of all the scenarios I did to make sure it all worked, but I'll admit to not doing it as formal unit tests. BAD developer. ;-)