确定两个日期范围是否重叠

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

例如,假设我们有一个用 DateTime 变量StartDate1EndDate1 以及 StartDate2EndDate2表示的范围。

答案

(StartA <= EndB)和(EndA> = StartB)

证明:
让 ConditionA 表示 DateRange A 完全在 DateRange B 之后
_ |---- DateRange A ------| |---Date Range B -----| _
(如果StartA > EndB真)

让 ConditionB 表示 DateRange A 完全早于 DateRange B
|---- DateRange A -----| _ _ |---Date Range B ----|
(如果EndA < StartB真)

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

现在, De Morgan 的一项法律规定

Not (A Or B) <=> Not A And Not B

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


注意:这包括边缘完全重叠的条件。如果您希望排除在外,
>=运算符更改为> ,将<=更改为<


笔记 2。感谢 @Baodad,请参阅此博客 ,实际重叠至少是:
{ endA-startAendA - startBendB-startAendB - startB }

(StartA <= EndB) and (EndA >= StartB) (StartA <= EndB) and (StartB <= EndA)


注意 3。感谢 @tomosius,一个简短的版本显示为:
DateRangesOverlap = max(start1, start2) < min(end1, end2)
这实际上是较长实现的语法快捷方式,其中包括额外的检查,以验证开始日期在 endDates 或之前。从上面导出:

如果开始日期和结束日期可能不正确,即startA > endAstartB > endB ,那么您还必须检查它们的顺序是否正确,这意味着您必须添加两个其他有效性规则:
(StartA <= EndB) and (StartB <= EndA) and (StartA <= EndA) and (StartB <= EndB)或:
(StartA <= EndB) and (StartA <= EndA) and (StartB <= EndA) and (StartB <= EndB)
(StartA <= Min(EndA, EndB) and (StartB <= Min(EndA, EndB))或:
(Max(StartA, StartB) <= Min(EndA, EndB)

但是要实现Min()Max() ,您必须进行编码(使用 C 三进制来简洁):
(StartA > StartB? Start A: StartB) <= (EndA < EndB? EndA: EndB)

我相信,只要满足以下两个条件,就可以说两个范围重叠:

(StartDate1 <= EndDate2) and (StartDate2 <= EndDate1)

本文的. NET时间段库通过枚举PeriodRelation描述了两个时间段的关系:

// ------------------------------------------------------------------------
public enum PeriodRelation
{
    After,
    StartTouching,
    StartInside,
    InsideStartTouching,
    EnclosingStartTouching,
    Enclosing,
    EnclosingEndTouching,
    ExactMatch,
    Inside,
    InsideEndTouching,
    EndInside,
    EndTouching,
    Before,
} // enum PeriodRelation

在此处输入图片说明

对于时间关系(或其他任何区间关系)的推理,请考虑艾伦的区间代数 。它描述了两个间隔相对于彼此可能具有的 13 种可能的关系。您可以找到其他参考文献 -“艾伦间隔” 似乎是一个有效的搜索词。您还可以在 Snodgrass 的SQL 中开发面向时间的应用程序中找到有关这些操作的信息(URL 可在线获取 PDF),以及 Date,Darwen 和 Lorentzos 的Temporal Data and Relational Model (2002)或Time and Relational Theory:Temporal Databases 中的内容。关系模型和 SQL (2014 年;有效的 TD&RM 第二版)。


简短的答案是:给定两个日期间隔AB ,其成分为.start.end ,约束为.start <= .end ,则两个间隔在以下情况下重叠:

A.end >= B.start AND A.start <= B.end

您可以调整>= vs ><= vs <以满足重叠程度的要求。


ErikE 评论:

如果把事情搞怪的话,你只能得到 13 个…… 当我发疯时,我可以得到 “两个区间可以具有的 15 个可能的关系”。通过明智的计算,我只有 6 个,如果您不关心 A 或 B 是第一个,则我只有 3 个(无相交,部分相交,一个完全相交)。 15 像这样:[before:before,start,inside,end,after],[start:start,inside,end,after],[within:within,end,after],[end:end,after],[after:after]。

我认为您不能计算 “before:before” 和 “after:after” 这两个条目。如果将它们的逆关系等同起来,我可以看到 7 个条目(请参见参考的 Wikipedia URL 中的图;它有 7 个条目,其中 6 个具有不同的逆,而等号没有明显的逆)。而三个是否明智取决于您的要求。

----------------------|-------A-------|----------------------
    |----B1----|
           |----B2----|
               |----B3----|
               |----------B4----------|
               |----------------B5----------------|
                      |----B6----|
----------------------|-------A-------|----------------------
                      |------B7-------|
                      |----------B8-----------|
                         |----B9----|
                         |----B10-----|
                         |--------B11--------|
                                      |----B12----|
                                         |----B13----|
----------------------|-------A-------|----------------------

如果还应该计算重叠本身,则可以使用以下公式:

overlap = max(0, min(EndDate1, EndDate2) - max(StartDate1, StartDate2))
if (overlap > 0) { 
    ...
}

通过确保特定范围开始得较早,就可以大大简化基于范围之间的相对位置检查多种条件的所有解决方案您可以通过在必要时预先交换范围来确保第一个范围更早(或同时)开始。

然后,如果另一个范围起点小于或等于第一个范围终点(如果包含范围,则包含开始时间和结束时间)或小于(如果范围包括起点并且不包含终点),则可以检测到重叠。

假设两端都具有包容性,则只有四种可能性,其中一种是非重叠的:

|----------------------|        range 1
|--->                           range 2 overlap
 |--->                          range 2 overlap
                       |--->    range 2 overlap
                        |--->   range 2 no overlap

范围 2 的端点没有输入。因此,用伪代码:

def doesOverlap (r1, r2):
    if r1.s > r2.s:
        swap r1, r2
    if r2.s > r1.e:
        return false
    return true

这可以进一步简化为:

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

如果范围在开始时是包含性的,而在结束时是排他性的,则只需在第二条if语句中用>=替换> (对于第一个代码段:在第二个代码段中,您将使用<而不是<= ):

|----------------------|        range 1
|--->                           range 2 overlap
 |--->                          range 2 overlap
                       |--->    range 2 no overlap
                        |--->   range 2 no overlap

您极大地限制了必须执行的检查次数,因为通过确保范围 1 在范围 2 之后永远不会开始,可以尽早消除问题空间的一半。

这是使用 JavaScript 的另一种解决方案。我的解决方案的特色:

  • 将空值处理为无穷大
  • 假设下限是包含的,上限是排他的。
  • 附带一堆测试

测试基于整数,但是由于 JavaScript 中的日期对象具有可比性,因此您也可以只放入两个日期对象。或者,您可以输入毫秒级的时间戳。

码:

/**
 * Compares to comparable objects to find out whether they overlap.
 * It is assumed that the interval is in the format [from,to) (read: from is inclusive, to is exclusive).
 * A null value is interpreted as infinity
 */
function intervalsOverlap(from1, to1, from2, to2) {
    return (to2 === null || from1 < to2) && (to1 === null || to1 > from2);
}

测试:

describe('', function() {
    function generateTest(firstRange, secondRange, expected) {
        it(JSON.stringify(firstRange) + ' and ' + JSON.stringify(secondRange), function() {
            expect(intervalsOverlap(firstRange[0], firstRange[1], secondRange[0], secondRange[1])).toBe(expected);
        });
    }

    describe('no overlap (touching ends)', function() {
        generateTest([10,20], [20,30], false);
        generateTest([20,30], [10,20], false);

        generateTest([10,20], [20,null], false);
        generateTest([20,null], [10,20], false);

        generateTest([null,20], [20,30], false);
        generateTest([20,30], [null,20], false);
    });

    describe('do overlap (one end overlaps)', function() {
        generateTest([10,20], [19,30], true);
        generateTest([19,30], [10,20], true);

        generateTest([10,20], [null,30], true);
        generateTest([10,20], [19,null], true);
        generateTest([null,30], [10,20], true);
        generateTest([19,null], [10,20], true);
    });

    describe('do overlap (one range included in other range)', function() {
        generateTest([10,40], [20,30], true);
        generateTest([20,30], [10,40], true);

        generateTest([10,40], [null,null], true);
        generateTest([null,null], [10,40], true);
    });

    describe('do overlap (both ranges equal)', function() {
        generateTest([10,20], [10,20], true);

        generateTest([null,20], [null,20], true);
        generateTest([10,null], [10,null], true);
        generateTest([null,null], [null,null], true);
    });
});

使用 karma&jasmine&PhantomJS 运行时的结果:

PhantomJS 1.9.8(Linux):执行 20 之 20 成功(0.003 秒 / 0.004 秒)

我会做

StartDate1.IsBetween(StartDate2, EndDate2) || EndDate1.IsBetween(StartDate2, EndDate2)

IsBetween在哪里像

public static bool IsBetween(this DateTime value, DateTime left, DateTime right) {
        return (value > left && value < right) || (value < left && value > right);
    }

在此处输入图片说明

这是执行魔术的代码:

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 尾

证明?查看此测试控制台代码要点

这是我在Java 中的解决方案,它也可以无限制地工作

private Boolean overlap (Timestamp startA, Timestamp endA,
                         Timestamp startB, Timestamp endB)
{
    return (endB == null || startA == null || !startA.after(endB))
        && (endA == null || startB == null || !endA.before(startB));
}