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

Question

我在数据库中有一张表，用于存储可以租借几天的物品。

现在每当有人租赁一个物品时，他们会指定一个起始日期和一个结束日期（基本上是他们想要租借该物品的日期范围）。

我想知道，在时间复杂度方面，检查输入的日期范围是否与数据库中已有的日期范围重叠的有效算法是什么。

说明：

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

注意:

这个问题不是这个问题的重复。那一个检查两个日期范围是否重叠。我的问题是关于一个输入日期范围与多个现有日期范围重叠的。

另一个说明:

如果您对这个问题的标签感到困惑，我可以接受两种类型的答案，与语言无关和特定语言。

对于那些想给出特定语言答案的人，以下是更多细节:

我有一个在python 3.4上运行，带有PostgreSQL数据库的Django 1.9项目。我的模型是：

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

- Amrullah Zunzunia

Answer 1

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

在您的系统中保留两个有序列表 - 一个用于“开始日期”，另一个用于“结束日期”。这些列表显然需要有一种方法来找到另一个列表中对应的项目。 收到新的输入时，找到小于新输入“开始日期”的最大“开始日期”，并检查相关的“结束日期”是否也小于新的“开始日期”，否则新输入是非法的。

同样适用于“结束日期”，只是相反的方式。

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

- shapiro yaacov

---

你的答案看起来非常有前途，能否请您至少给一些提示，说明如何使用树来完成这个任务？ - Amrullah Zunzunia

当然。不要使用有序列表，而是使用树。AVL、红黑或2-3树都承诺这些操作的O(log n)性能... - shapiro yaacov

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

- raratiru