Determine whether input date range overlaps with existing ones

Question

I have a table in database which stores items that can be rented for a period of few days.

Now whenever someone rents an item, they specify a start_date and an end_date(basically a date range for which they want to rent that item).

I want to know what is the efficient algorithm (in terms of time complexity) to check that input date range doesn't overlap with 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. That one checks whether two date ranges overlap. My question is about an input date range overlapping with multiple existing date ranges

Another Note:

In case you are confused by this question's tags, I am open to both kind of answers, language-agnostic as well as language-specific.

For those who want to give language-specific answer, here are more details:

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

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()

score 2 · Accepted Answer · answered Jun 21 '16 at 07:54

2

This answer assumes that all previous input is legal. In case not, it can be altered to fit other scenarios.

Keep two ordered lists in your system - one for the start dates and one for the end dates. These list will obviously need to have a way to find the correlating item in the other list. When receiving a new input, find the largest start date that is smaller than the new inputs' start date and check that the relevant end date is also smaller than the new start date, otherwise the new input is illegal.

Same goes for the end date, just the other way round.

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

answered Jun 21 '16 at 07:54

shapiro yaacov

2,308
2
26
39

1

your answer looks very promising, can you please give at least some hint on how this can be done using trees? – Amrullah Zunzunia Jun 21 '16 at 08:25
1

Sure. Instead of using an ordered list, use a tree. The AVL, black-red or 2-3 trees all promise `O(log n)` performance for these actions... – shapiro yaacov Jun 21 '16 at 08:54

score 1 · Answer 2 · answered Oct 15 '19 at 13:18

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

Determine whether input date range overlaps with existing ones

2 Answers2