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

Question

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

举个例子,假设我们有通过日期时间变量表示的范围StartDate1来EndDate1 和 StartDate2到EndDate2.

Answer 1

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

证明:
让ConditionA意味着DateRange完全在DateRange B之后
_ |---- DateRange A ------| |---Date Range B -----| _
(如果是,则为True StartA > EndB)

让ConditionB表示DateRange A完全在DateRange B之前
|---- DateRange A -----| _ _ |---Date Range B ----|
(如果是,则为True EndA < StartB)

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

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

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

这意味着: (StartA <= EndB) and (EndA >= StartB)

注意:这包括边缘完全重叠的条件.如果你想排除,
改变>=运营商>,并<= 以<

笔记2.由于@Baodad,看到这个博客,实际的重叠是最少:
{ endA-startA,endA - startB,endB-startA,endB - startB}

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

注3.感谢@tomosius,更短的版本读取:
DateRangesOverlap = max(start1, start2) < min(end1, end2)
这实际上是更长实现的语法快捷方式,其中包括额外的检查以验证开始日期是在endDates之前还是之前.从上面得出这个:

如果开始日期和结束日期可能不正常,即,如果有可能startA > endA或者startB > 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(),你必须代码,(使用简洁Ç三元),:
(StartA > StartB? Start A: StartB) <= (EndA < EndB? EndA: EndB)

Answer 2

我认为,如果符合以下条件,两个范围重叠就足够了:

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

Answer 3

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

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

Answer 4

关于时间关系(或任何其他区间关系,来到那里)的推理,考虑艾伦的区间代数.它描述了两个间隔相对于彼此可能具有的13种可能的关系.您可以找到其他参考文献 - "Allen Interval"似乎是一个可操作的搜索词.您还可以在Snodgrass 开发的面向时间的SQL应用程序中找到有关这些操作的信息(可通过URL在线获取PDF),以及Date,Darwen和Lorentzos时态数据和关系模型(2002)或 时间和关系理论:时间数据库.关系模型和SQL(2014年;实际上是TD&RM的第二版).

短(ish)答案是:给定两个日期间隔A以及B组件.start和.end约束.start <= .end,如果出现以下情况,则两个间隔重叠:

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

您可以调整>=vs >和<=vs 的使用,<以满足您对重叠程度的要求.

ErikE评论:

如果算上有趣的话,你只能获得13分......当我疯狂的时候,我可以得到"15个可能有两个间隔的关系".通过合理的计数,我只得到6,如果你抛出关心A或B是否先出现,我只得到三个(没有交叉,部分交叉,一个完全在另一个内).15是这样的:[之前:之前,开始,之内,结束,之后],[开始:开始,内部,结束,之后],[内部:内部,结束,之后],[结束:结束,之后],[后:后.

我认为你不能把这两个条目计算在:之前'和'之后:之后'.如果你把一些关系等同于它们的反转,我可以看到7个条目(参见引用的维基百科URL中的图表;它有7个条目,其中6个具有不同的反转,等于没有明显的反转).三个是否合理取决于您的要求.

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

Answer 5

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

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

Answer 6

通过确保特定范围更早开始,可以极大地简化基于范围相互关联的多种条件检查的所有解决方案!您可以通过在必要时预先交换范围来确保第一个范围更早(或同时)开始.

然后,如果其他范围开始小于或等于第一个范围结束(如果范围包含,包含开始和结束时间)或小于(如果范围包括开始和排除结束),则可以检测重叠.

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

|----------------------|        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之后开始,您可以提前删除一半的问题空间.

Answer 7

这是使用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秒)

Answer 8

我会做

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);
    }

Answer 9

记住解决方案的一种简单方法是
min(ends)>max(starts)

Answer 10

这是我在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));
}

Answer 11

这是执行魔术的代码:

 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结束

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

Answer 12

此处发布的解决方案不适用于所有重叠范围......

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

我的工作解决方案是:

AND (
  ('start_date' BETWEEN STARTDATE AND ENDDATE) -- caters for inner and end date outer
  OR
  ('end_date' BETWEEN STARTDATE AND ENDDATE) -- caters for inner and start date outer
  OR
  (STARTDATE BETWEEN 'start_date' AND 'end_date') -- only one needed for outer range where dates are inside.
) 

Answer 13

由于针对不同的语言和环境有多种答案，这里有一个针对标准 ANSI SQL 的答案。

在标准 SQL 中，它就像这样简单

(StartDate1, EndDate1) overlaps (StartDate2, EndDate2)

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

（但是并非所有 DBMS 产品都支持）

在 PostgreSQL 中，通过使用日期范围来测试包含也很容易

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

如果第二个范围完全包含在第一个范围中（这与“重叠”不同），则以上返回 true

Answer 14

这是我用moment.js的javascript解决方案:

// Current row dates
var dateStart = moment("2014-08-01", "YYYY-MM-DD");
var dateEnd = moment("2014-08-30", "YYYY-MM-DD");

// Check with dates above
var rangeUsedStart = moment("2014-08-02", "YYYY-MM-DD");
var rangeUsedEnd = moment("2014-08-015", "YYYY-MM-DD");

// Range covers other ?
if((dateStart <= rangeUsedStart) && (rangeUsedEnd <= dateEnd)) {
    return false;
}
// Range intersects with other start ?
if((dateStart <= rangeUsedStart) && (rangeUsedStart <= dateEnd)) {
    return false;
}
// Range intersects with other end ?
if((dateStart <= rangeUsedEnd) && (rangeUsedEnd <= dateEnd)) {
    return false;
}

// All good
return true;

Answer 15

这是@charles-bretana优秀答案的扩展。

然而，答案并没有区分开区间、闭区间和半开（或半闭）区间。

情况1：A、B是闭区间

A = [StartA, EndA]
B = [StartB, EndB]

                         [---- DateRange A ------]   (True if StartA > EndB)
[--- Date Range B -----]                           


[---- DateRange A -----]                             (True if EndA < StartB)
                         [--- Date Range B ----]

重叠当且仅当：(StartA <= EndB) and (EndA >= StartB)

情况2：A，B是开区间

A = (StartA, EndA)
B = (StartB, EndB)

                         (---- DateRange A ------)   (True if StartA >= EndB)
(--- Date Range B -----)                           

(---- DateRange A -----)                             (True if EndA <= StartB)
                         (--- Date Range B ----)

重叠当且仅当：(StartA < EndB) and (EndA > StartB)

情况3：A、B右开

A = [StartA, EndA)
B = [StartB, EndB)

                         [---- DateRange A ------)   (True if StartA >= EndB) 
[--- Date Range B -----)                           

[---- DateRange A -----)                             (True if EndA <= StartB)
                         [--- Date Range B ----)

重叠条件：(StartA < EndB) and (EndA > StartB)

情况 4：A、B 保持开路

A = (StartA, EndA]
B = (StartB, EndB]

                         (---- DateRange A ------]   (True if StartA >= EndB)
(--- Date Range B -----]                           

(---- DateRange A -----]                             (True if EndA <= StartB)
                         (--- Date Range B ----]

重叠条件：(StartA < EndB) and (EndA > StartB)

情况5：A右开，B右闭

A = [StartA, EndA)
B = [StartB, EndB]

                         [---- DateRange A ------)    (True if StartA > EndB)
[--- Date Range B -----]                           


[---- DateRange A -----)                              (True if EndA <= StartB)  
                         [--- Date Range B ----]

重叠条件：(StartA <= EndB) and (EndA > StartB)

ETC...

最后，两个区间重叠的一般条件是

（开始 A < 结束 B）和（结束 A > 开始 B）

每当在两个包含的端点之间进行比较时，其中就会将严格不等式转换为非严格不等式。

Answer 16

使用 momentjs 的简短回答：

function isOverlapping(startDate1, endDate1, startDate2, endDate2){ 
    return moment(startDate1).isSameOrBefore(endDate2) && 
    moment(startDate2).isSameOrBefore(endDate1);
}

答案基于上述答案，但缩短了。