Determine if the input date range matches the existing

Question

I have a table in the database that stores items that can be rented for several days.

Now that someone is renting an item , they indicate start_date and end_date (basically a date range for which they want to rent this item ).

I want to know what is an efficient algorithm (in terms of time complexity) to verify that the input of date range does not overlap with the existing date ranges in the database.

Illustration:

 |<------existing 1------->| |<------existing 2------->| |<------ input date range ---->| (which clearly, overlaps) 

Note:

This question is not a duplicate of this question. This checks if the two date ranges overlap. My question is about entering date range overriding several existing date ranges

Another note:

If you are confused by these question tags, I am open to both answers: language-agnostic as well as language-specific .

For those who want to give a language-specific answer, here is more detailed information:

I have a django 1.9 project running on python 3.4 with PostgreSQL as a database. My models:

 class Item(models.Model): name = models.CharField(max_length=100) class BookingPeriod(models.Model): item = models.ForeignKey(Item) start_date = models.DateField() end_date = models.DateField() 

Answer 1

This answer assumes that all previous input is legal. If not, it can be changed to fit other scenarios.

Save two ordered lists on your system - one for start date and one for end date s. Obviously, this list should find a way to find the correlating element in another list. When receiving a new input, find the largest start date , which is less than the new start date entries, and check that the corresponding end date also less than the new start date , otherwise the new entry is illegal.

The same goes for end date , vice versa.

I think this can be done (using trees instead of lists) in O(log n) .

Answer 2

Here is some code that achieves this result:

 def validate_overlap(periods, count_days=True): """ Receives a list with DateRange or DateTimeRange and returns True if periods overlap. In this application it is guaranteed that the end of each period is not inclusive. Therefore if a period ends in 15/5 and another starts in 15/5, they do not overlap. The same with datetime periods. """ periods.sort() no_overlap = [True] for each in range(0, len(periods) - 1): latest_start = max(periods[each].lower, periods[each + 1].lower) earliest_end = min(periods[each].upper, periods[each + 1].upper) delta = earliest_end - latest_start if count_days: no_overlap.append(max(0, delta.days) == 0) else: no_overlap.append(max(0, delta.total_seconds()) == 0) return False if all(no_overlap) else True