确定输入日期范围是否与现有日期范围重叠

Question

我在数据库中有一张存储items的桌子，可以租用几天。

现在，只要有人租了一个item，他们就会指定一个start_date和一个end_date(基本上是一个想要租给这个item的date range )。

我想知道什么是有效的算法(就时间复杂度而言)，以检查输入date range是否与数据库中的现有date ranges重叠。

插图：

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

注：

这个问题不是this问题的重复。一个检查两个date ranges是否重叠。我的问题是与多个现有的date range重叠的输入date ranges。

另一个注意事项：

如果你被这个问题的标签弄糊涂了，我对language-agnostic和language-specific这两种答案都是开放的。

对于那些想给language-specific答案的人，这里有更多的细节：

我在python 3.4上运行了一个以PostgreSQL为数据库的PostgreSQL项目。我的模特是：

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

这个答案假定以前的所有输入都是合法的。如果不是，可以修改它以适应其他情况。

在您的系统中保留两个有序列表-一个用于start date，另一个用于end date。显然，这些列表需要在另一个列表中找到相关项。接收新输入时，找到比新输入的start date小的最大start date，并检查相关的end date是否也小于新的start date，否则新输入是非法的。

end date也是如此，正好相反。

我认为这可以在O(log n)中完成(使用树而不是列表)。

Answer 2

以下是实现此结果的一些代码：

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