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

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


当前回答

public static class NumberExtensionMethods
    {
        public static Boolean IsBetween(this Int64 value, Int64 Min, Int64 Max)
        {
            if (value >= Min && value <= Max) return true;
            else return false;
        }

        public static Boolean IsBetween(this DateTime value, DateTime Min, DateTime Max)
        {
            Int64 numricValue = value.Ticks;
            Int64 numericStartDate = Min.Ticks;
            Int64 numericEndDate = Max.Ticks;

            if (numricValue.IsBetween(numericStartDate, numericEndDate) )
            {
                return true;
            }

            return false;
        }
    }

public static Boolean IsOverlap(DateTime startDate1, DateTime endDate1, DateTime startDate2, DateTime endDate2)
        {
            Int64 numericStartDate1 = startDate1.Ticks;
            Int64 numericEndDate1 = endDate1.Ticks;
            Int64 numericStartDate2 = startDate2.Ticks;
            Int64 numericEndDate2 = endDate2.Ticks;

            if (numericStartDate2.IsBetween(numericStartDate1, numericEndDate1) ||
                numericEndDate2.IsBetween(numericStartDate1, numericEndDate1) ||
                numericStartDate1.IsBetween(numericStartDate2, numericEndDate2) ||
                numericEndDate1.IsBetween(numericStartDate2, numericEndDate2))
            {
                return true;
            }

            return false;
        } 


if (IsOverlap(startdate1, enddate1, startdate2, enddate2))
            {
                Console.WriteLine("IsOverlap");
            }

其他回答

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

       | |
     | |

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

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

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

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

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

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

例如(假设两端都包含),范围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

其中每条线具有:

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

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

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

答案对我来说太简单了,所以我创建了一个更通用的动态SQL语句,用于检查某人是否有重叠的日期。

SELECT DISTINCT T1.EmpID
FROM Table1 T1
INNER JOIN Table2 T2 ON T1.EmpID = T2.EmpID 
    AND T1.JobID <> T2.JobID
    AND (
        (T1.DateFrom >= T2.DateFrom AND T1.dateFrom <= T2.DateTo) 
        OR (T1.DateTo >= T2.DateFrom AND T1.DateTo <= T2.DateTo)
        OR (T1.DateFrom < T2.DateFrom AND T1.DateTo IS NULL)
    )
    AND NOT (T1.DateFrom = T2.DateFrom)

为了涵盖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的范围之间。

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

(起点A<=终点B)和(终点A>=起点B)

证明:让条件A表示日期范围A完全在日期范围B之后

_                        |---- DateRange A ------|
|---Date Range B -----|                          _

(如果StartA>EndB,则为True)

让条件B表示日期范围A完全在日期范围B之前

|---- DateRange A -----|                        _ 
_                          |---Date Range B ----|

(如果EndA<StartB,则为True)

如果A和B都不为真,则存在重叠-(如果一个范围既不完全在另一个范围之后,也不完全在另一个之前,则它们必须重叠。)

现在,德摩根的一项法律规定:

不是(A或B)<=>不是A也不是B

转换为:(StartA<=EndB)和(EndA>=StartB)


注意:这包括边缘完全重叠的情况。如果你想排除这一点,将>=运算符更改为>,并将<=更改为<


注2.多亏了@宝爸,看看这个博客,实际的重叠最少:{endA startA,endA-startB,endB startA,end B-startB}

(起点A<=终点B)和(终点A>=起点B)(开始A<=结束B)和(开始B<=结束A)


注3.多亏了@tomosius,一个简短的版本写道:DateRangesOverlap=最大值(start1,start2)<最小值(end1,end2)这实际上是一个较长实现的语法快捷方式,它包括额外的检查,以验证开始日期是否在结束日期之前。从上面得出:

如果开始日期和结束日期可能是无序的,即,如果startA>endA或startB>endB是可能的,那么您还必须检查它们是否有序,这意味着您必须添加两个额外的有效性规则:(StartA<=EndB)和(StartB<=EndA)以及或:(开始A<=结束B)和(开始A<=结束A)以及(开始B<=结束A”和(开始B<=结束B”)或(开始A<=最小值(结束A,结束B)和(开始B<=最小(结束A、结束B))或:(最大值(开始A,开始B)<=最小值(结束A,结束B)

但要实现Min()和Max(),必须编写代码(使用C三进制表示简洁):((开始A>开始B)?开始A:开始B)<=((结束A<结束B)?端A:端B)