An efficient algorithm to check date range overlap

TL;DR: use SQL end_date2 >= start_date1 and end_date1 >= start_date2.

Problem

Picture this. A real estate site’s guest wants to book a hotel for specific dates. The system should check whether these dates are available, i.e. if they don’t overlap with an existing booking. Let’s say software engineers have written this hypothetical site in Rails and have come up with a Booking model. It represents the bookings table with two columns: start_date and end_date of date type. Also suppose there is a validation somewhere checking start_date <= end_date. The solution below describes how to cope with this specific situation. Similar data models can follow it, though.

Solution

Probably, the easiest solution to this problem would be the Rails way. Just define a custom validation inside the Booking model that runs whenever a new booking is created or an existing one is updated:

class Booking < ApplicationRecord
  # ... some code is skipped here for simplicity's sake
  validate :validate_other_booking_overlap

  def period
    start_date..end_date
  end

  private

  def validate_other_booking_overlap
    other_bookings = Booking.all
    is_overlapping = other_bookings.any? do |other_booking|
      period.overlaps?(other_booking.period)
    end
    errors.add(:overlaps_with_other) if is_overlapping
  end
end

But unfortunately, there is a performance bottleneck here. Keep in mind that all the bookings are fetched from the database first. Then they are deserialized into Booking model instances. After that the period of each is checked against the Booking instance being created or updated. At first glance — such simple code, but how many complicated things it actually does! It creates so many objects consuming a lot of memory on the machine running this code. That is actually the main reason for software slowness. Yet, sometimes this attempt can be viable, i.e. when the number of objects fetched from DB is not high. Whether to go with it or not is up to the developer and should be chosen wisely considering the possible drawback.

If this approach doesn’t work, we should look for a new one. What can be done to improve this? In order to answer this question, the root cause of the problem should be understood. And it’s actually highlighted above - the number of allocated objects is huge. Hence, we need to reduce it. A possible way could be moving the loop into the DB, and luckily ActiveRecord accepts SQL. This is the code one might end up with using PostgreSQL:

def validate_other_booking_overlap
  sql = "daterange(start_date, end_date, '[]') && daterange(:start_date, :end_date, '[]')"
  is_overlapping = Booking.where(sql, start_date: c.start_date, end_date: c.end_date).exists?
  errors.add(:overlaps_with_other) if is_overlapping
end

Read the statement daterange(start_date, end_date, '[]') as “create a range of dates from start_date to end_date, including both endpoints”. The third argument [] points to the property of inclusiveness. More about this can be found here.

The && operator is used here to check for overlapping ranges. Check out the documentation if any questions arise.

What’s the issue with this attempt? Well, this code is much more efficient compared to the first one. But it still creates objects for the date ranges, at the DB level this time, however. Remember, an unnecessary number of objects causes a program to run slowly. That’s why, if possible, the number of allocations should be reduced. This code is literally translated from the previous version emphasizing readability. Therefore, even after the into-SQL transformation it is more or less readable. But how to speed it up? This time the readability emphasis is the key. Often, to fix performance issues, the current solution may be rewritten in a more efficient way. But this usually sacrifices clarity. Trying this way one may end up with the following SQL:

sql = <<~SQL
  (
    (start_date <= :start_date and :start_date <= end_date) or
    (start_date <= :end_date and :end_date <= end_date)
  ) or (
    (:start_date <= start_date and start_date <= :end_date) or
    (:start_dae <= end_date and end_date <= :end_date)
  )
SQL

The rest of the code is omitted because it remains the same. From now on, only the line defining the sql variable in the validation method changes.

It simply checks whether any edge of the first range is inside the second one. Or whether any edge of the second range is inside the first one. This choice allocates even fewer objects, so it must be faster than the previous one. But look at this - it’s a bit cumbersome. Can it be better? It turns out it can:

sql = ":end_date >= start_date and end_date >= :start_date"

What is the logic behind this formula? Ranges overlap if and only if they are not separated to the left and are not separated to the right. Or the following doesn’t happen:

                      start_date          end_date
                          |--------------------|
:start_date     :end_date
|-------------------|

or

start_date          end_date
    |--------------------|
                           :start_date        :end_date
                              |-------------------|

The proof of this is rather obvious: all possible situations could be drawn and checked. After that it would be clear that all other cases intersect.

Transform this statement into a boolean formula:

not (:end_date < start_date or end_date < :start_date)

Get rid of the leading negation and replace all statements inside the parentheses with their negations:

=>

not (:end_date < start_date) and not (end_date < :start_date)

=>

:end_date >= start_date and end_date >= :start_date

If this explanation is not clear, please check it.

The final formula is derived. But are there any downsides? Well, it’s a matter of taste. On the one hand, it’s less readable than the Rails-style solution. On the other hand, it’s the most efficient one we’ve come up with so far. If someone thinks this trick is not clear, documentation could be provided. So everyone reading this code could understand what’s hidden behind it.

Conclusion

This article provides a solution to a rather common problem: overlapping date ranges. Sometimes it’s hard to tackle a specific problem while balancing clarity and efficiency. This journey is meant to demonstrate that balance and lead to a solution.

Credit goes to the colleagues who reviewed my pull request solving a similar problem. The suggested final approach was not clear to me and even seemed not to work. But a bit of thinking made me change my opinion. That process of thinking and the proof were pretty interesting. It made me write this down.

Never give up finding a good solution to your problem. There is always an opportunity to improve. Happy coding!