给定两个日期范围,确定两个日期是否重叠的最简单或最有效的方法是什么?

例如,假设我们有由DateTime变量StartDate1到EndDate1和StartDate2到EndDate2表示的范围。


当前回答

由于对于不同的语言和环境有多种答案,这里有一个标准ANSISQL的答案。

在标准SQL中,它非常简单

(StartDate1, EndDate1) overlaps (StartDate2, EndDate2)

假设所有四列都是DATE或TIMESTAMP列。如果两个范围至少有一天相同(假设DATE值),则返回true

(但并非所有DBMS产品都支持此功能)


在PostgreSQL中,使用日期范围也很容易测试是否包含

daterange(StartDate1, EndDate1) @> daterange(StartDate2, EndDate2)

如果第二个范围完全包含在第一个范围中(与“重叠”不同),则上述值返回真

其他回答

我认为最简单的方法是比较EndDate1是否在StartDate2之前,EndDate2是否在StartDate 1之前。

当然,如果您正在考虑StartDate总是在EndDate之前的时间间隔。

通过简单地确保一个范围在另一个范围之前或同时开始,可以大大简化基于范围之间的关系来检查大量条件的所有解决方案。如果需要,您可以在前面交换范围。

然后,如果第二个范围开始是:

小于或等于第一范围结束(如果包含范围,则包含开始时间和结束时间);或小于(如果范围包括开始,不包括结束)。

例如(假设两端都包含),范围2只有四种可能性,其中一种是不重叠的(范围末尾的>表示范围结束的位置无关紧要):

|-----|        range 1, lines below are all range 2.
|-->  :        overlap.
 |--> :        overlap.
      |--->    overlap (no overlap in exclusive-of-end case).
       |--->   no overlap.

第二个范围的端点根本不会影响结果。因此,在伪代码中,您可以执行以下操作(假设s<=e适用于所有范围-如果不适用,您也可以进行顶部交换):

def overlaps(r1, r2):
    if r1.s > r2.s:
        swap r1, r2
    return r2.s <= r1.e

或者,一级限制递归选项:

def overlaps(r1, r2):
    if r1.s <= r2.s:
        return r2.s <= r1.e
    return overlaps(r2, r1)

如果范围在最后是排他的,则只需在返回的表达式中(在两个代码片段中)将<=替换为<即可。

这大大限制了您必须进行的检查的数量,因为您通过确保第一个范围不会在第二个范围之后开始,提前删除了一半的问题空间。


而且,由于“代码说话”,这里有一些Python代码在实际操作中显示了这一点,其中包含了相当多的测试用例。首先,InclusiveRange类:

class InclusiveRange:
    """InclusiveRange class to represent a lower and upper bound."""

    def __init__(self, start, end):
        """Initialisation, ensures start <= end.
        Args:
            start: The start of the range.
            end: The end of the range.
        """
        self.start = min(start, end)
        self.end = max(start, end)

    def __repr__(self):
        """Return representation for f-string."""
        return f"({self.start}, {self.end})"

    def overlaps(self, other):
        """True if range overlaps with another.
        Args:
            other: The other InclusiveRange to check against.
        """

        # Very limited recursion to ensure start of first range
        # isn't after start of second.

        if self.start > other.start:
            return other.overlaps(self)

        # Greatly simplified check for overlap.

        return other.start <= self.end

然后是一个测试用例处理程序,允许我们很好地呈现单个测试用例的结果:

def test_case(range1, range2):
    """Single test case checker."""

    # Get low and high value for "graphic" output.

    low = min(range1.start, range2.start)
    high = max(range1.end, range2.end)

    # Output ranges and graphic.

    print(f"r1={range1} r2={range2}: ", end="")
    for val in range(low, high + 1):
        is_in_first = range1.start <= val <= range1.end
        is_in_second = range2.start <= val <= range2.end

        if is_in_first and is_in_second:
            print("|", end="")
        elif is_in_first:
            print("'", end="")
        elif is_in_second:
            print(",", end="")
        else:
            print(" ", end="")

    # Finally, output result of overlap check.

    print(f" - {range1.overlaps(range2)}\n")

最后,如果需要,可以添加自己的测试用例:

# Various test cases, add others if you doubt the correctness.

test_case(InclusiveRange(0, 1), InclusiveRange(8, 9))
test_case(InclusiveRange(0, 4), InclusiveRange(5, 9))
test_case(InclusiveRange(0, 4), InclusiveRange(4, 9))
test_case(InclusiveRange(0, 7), InclusiveRange(2, 9))
test_case(InclusiveRange(0, 4), InclusiveRange(0, 9))
test_case(InclusiveRange(0, 9), InclusiveRange(0, 9))
test_case(InclusiveRange(0, 9), InclusiveRange(4, 5))

test_case(InclusiveRange(8, 9), InclusiveRange(0, 1))
test_case(InclusiveRange(5, 9), InclusiveRange(0, 4))
test_case(InclusiveRange(4, 9), InclusiveRange(0, 4))
test_case(InclusiveRange(2, 9), InclusiveRange(0, 7))
test_case(InclusiveRange(0, 9), InclusiveRange(0, 4))
test_case(InclusiveRange(0, 9), InclusiveRange(0, 9))
test_case(InclusiveRange(4, 5), InclusiveRange(0, 9))

产生输出的运行:

r1=(0, 1) r2=(8, 9): ''      ,, - False
r1=(0, 4) r2=(5, 9): ''''',,,,, - False
r1=(0, 4) r2=(4, 9): ''''|,,,,, - True
r1=(0, 7) r2=(2, 9): ''||||||,, - True
r1=(0, 4) r2=(0, 9): |||||,,,,, - True
r1=(0, 9) r2=(0, 9): |||||||||| - True
r1=(0, 9) r2=(4, 5): ''''||'''' - True
r1=(8, 9) r2=(0, 1): ,,      '' - False
r1=(5, 9) r2=(0, 4): ,,,,,''''' - False
r1=(4, 9) r2=(0, 4): ,,,,|''''' - True
r1=(2, 9) r2=(0, 7): ,,||||||'' - True
r1=(0, 9) r2=(0, 4): |||||''''' - True
r1=(0, 9) r2=(0, 9): |||||||||| - True
r1=(4, 5) r2=(0, 9): ,,,,||,,,, - True

其中每条线具有:

这两个范围被评估;“范围空间”(从最低开始到最高结束)的图形表示,其中每个字符都是“范围空间中的值”:'仅表示第一个范围内的值;,仅指示第二范围内的值;|表示两个范围中的值;和表示两个范围中的值。重叠检查的结果。

您可以非常清楚地看到,只有在两个范围中都至少有一个值(即,一个|字符)时,才能在重叠检查中获得真值。其他情况都是假的。

如果您想添加更多测试用例,请随意使用任何其他值。

这是一段神奇的代码:

 var isOverlapping =  ((A == null || D == null || A <= D) 
            && (C == null || B == null || C <= B)
            && (A == null || B == null || A <= B)
            && (C == null || D == null || C <= D));

哪里

A->1启动B->1结束C->2启动D->2结束

证据查看此测试控制台代码要点。

这里是我的简化。假设时间间隔

       | |
     | |

不要重叠,xa<xb和ya<yb可以简化处理。上述条件可以简单检查。然后你会得到

      ya       yb
      |--------|
xa |--|xb
   |----|
         |----|
ya > xa => return ya - xa < xb - xa
else    => return xa < yb

正如您可能注意到的,第二个间隔仅在xa>=ya的情况下相关。

为了涵盖PHP/LaravelCarbon包中的所有重叠情况,您可以在Charles的答案中展开逻辑,如下所示。

if ( ($startTime1->between($startTime2, $endTime2, true) || $endTime1->between($startTime2, $endTime2, true)) || (($startTime1 <= $endTime2) && ($endTime2 <= $endTime1)) ){
//Complete Overlap, Partial Left Overlap, Partial Right Overlap. 
}

这将检查StartTime1是否在(StartTime2-EndTime2)范围之间,或者EndTime1是否位于(StartTime2-EndTime2的范围之间。

其余部分完全重叠,如其他答案所述。