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

Question

我在数据库中有一个 table 存储 items 可以租用几天。

现在，每当有人租 item 时，他们都会指定 start_date 和 end_date（基本上是 date range，他们想租 item).

我想知道什么是有效算法（就时间复杂度而言）来检查输入 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 上有一个 django 1.9 项目运行，使用 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

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

Determine whether input date range overlaps with existing ones

language-agnostic

django

algorithm

date

python-3.x