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


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

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


986
2017-11-28 14:48


起源


非常相似 stackoverflow.com/questions/306316/... - Charles Bretana
@CharlesBretana感谢你,你是对的 - 这几乎就像我的问题的二维版本! - Ian Nelson
非常相似 stackoverflow.com/questions/117962/... - Steven A. Lowe
将情况“两个日期范围相交”分为案例(有两个),然后对每个案例进行测试。 - Colonel Panic
这段代码工作正常。你可以在这里看到我的答案: stackoverflow.com/a/16961719/1534785 - Jhoon Bey


答案:


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

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

设ConditionB表示DateRange A完全在DateRange B之前
|---- DateRange A -----| _ _ |---Date Range B ----|
 (如果确实如此 EndA < StartB

如果A Nor B都不成立则存在重叠 -
 (如果一个范围既不完全在另一个范围之后,
   也不完全在另一个之前,      然后他们必须重叠。)

现在其中之一 德摩根的法律 说:

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 > 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(),你必须编码,(使用C三元语言简洁),
(StartA > StartB? Start A: StartB) <= (EndA < EndB? EndA: EndB) 


1871
2017-11-28 15:00



这是基于这两个假设的简化逻辑:1)StartA <EndA; 2)StartB <EndB。这似乎是显而易见的,但实际上数据可能来自未知来源,如用户输入或没有消毒的数据库。请记住,您需要验证输入数据,以确保在使用此简化逻辑之前这两个假​​设是正确的,否则一切都将崩溃。从我自己的经验中吸取教训;) - Devy
@Devy,你是对的。除非它在startA = endA时也有效。的确,这正是这些话 Start 和 End 意思。如果你有两个名为Top和Bottom,或East和West,或HighValue和LoValue的变量,可以假设或暗示某个地方或某个人应该确保其中一对值没有存储在相反的变量中。 - 只有两对中的一对,因为如果切换两对值,它也会起作用。 - Charles Bretana
@rashid, 这是一篇文章 可能会给你一些关于如何获得实际重叠量的提示。 - Baodad
您可以轻松添加可空 start 和 end (语义为“null start”=“从时间的开头”和“null end”=“到时间结束”),如下所示: (startA === null || endB === null || startA <= endB) && (endA === null || startB === null || endA >= startB) - Kevin Robatel
Stackexchange的最佳答案!看到这个智能配方为何起作用的解释感觉很好! - Abeer Sul


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

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

320
2017-11-28 14:49



我找到了 (StartDate1 <= EndDate2) and (EndDate1 >= StartDate2) 符号更容易理解,Range1总是在测试中左侧。 - A.L
这假设开始日期和结束日期包括在内。更改 <= 至 < 如果start是包容性的并且end是独占的。 - Richard Schneider
即使startDate2在startDate1之前,这也能很好地工作。所以不需要假设startDate1早于startDate2。 - Shehan Simen
我发现(StartDate1 <= EndDate2)和(StartDate2 <= EndDate1)符号(根据答案)比其他答案更容易理解。 - apc


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

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

enter image description here


87
2018-04-08 22:42



很好,我也在Java中实现了Allens区间代数,请参阅 IntervalRelation和IsoInterval的API - Meno Hochschild


关于时间关系(或任何其他区间关系,来到那个)的推理,请考虑 艾伦的区间代数。它描述了两个间隔相对于彼此可能具有的13种可能的关系。您可以找到其他参考文献 - “Allen Interval”似乎是一个可操作的搜索词。您还可以在Snodgrass中找到有关这些操作的信息 在SQL中开发面向时间的应用程序 (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-------|----------------------

66
2017-11-30 06:54



如果算上有趣的事情,你只能获得13分......当我疯狂的时候,我可以得到“15个可能的关系,两个间隔可以有”。通过合理的计数,我只得到6,如果你抛出关心A或B是否先出现,我只得到三个(没有交叉,部分交叉,一个完全在另一个内)。 15是这样的:[之前:之前,开始,之内,之后,之后],[开始:开始,内部,结束,之后],[内部:内部,结束,之后],[结束:结束,之后],[后:后。 - ErikE
@Emtucifor:我认为你不能把这两个条目计算在:之前'和'之后:之后'。 - Jonathan Leffler
重新更新:B1到A在之前:之前,B13到A在之后:之后。你的漂亮图表缺少开始:在B5 B6之间开始,结束:在B11和B12之间结束。如果在端点上是重要的,那么你必须计算它,所以最终的计数是15,而不是13 别 认为端点的东西是重要的,所以我个人认为[之前:之前,之内,之后],[内部:内部,之后],[之后:之后]进入6.我认为整个端点的事情只是混乱边界是包容性的还是排他性的。端点的排他性不会改变核心关系! - ErikE
也就是说,在我的方案中,这些是等价的:(B2,B3,B4),(B6,B7,B9,B10),(B8,B11,B12)。我意识到B7意味着两个范围完全重合的信息。但我不相信这一点 额外 信息应该是基础交叉关系的一部分。例如,如果两个区间的长度完全相同,即使不重合甚至重叠,是否应将其视为另一个“关系”?我说不,并且看到这个额外的方面是使B7与B6区别开来的唯一因素,那么我认为有端点 - 作为单独的案例会使事情不一致。 - ErikE
@Emtucifor:好的 - 我明白为什么我错误地识别'之前:之前'和'之后:之后'作为条目;但是,我无法想象'start:start'和'end:end'条目应该是什么样子。由于您无法编辑我的图表,您是否可以通过图表的修改副本向我发送电子邮件(请参阅我的个人资料),其中显示了“开始:开始”和“结束:结束”关系?我的分组没有重大问题。 - Jonathan Leffler


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

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

25
2017-09-06 02:07



所以重叠是两个事件共享的时间量?这是否适用于事件可以重叠的所有不同方式? - NSjonas


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

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

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

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


16
2017-08-06 02:39



提及包容性/排他性问题的+1。当我有时间的时候,我会自己提出一个答案,但现在不需要。问题是你几乎从不允许开始和结束同时包容。在我的行业中,通常的做法是将起点视为包容性的,将结尾视为包容性,但只要保持一致,任何一种方式都可以。到目前为止,这是关于这个问题的第一个完全正确的答案...... IMO。 - Brian Gideon


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


12
2018-03-13 13:19





我知道这已被标记为与语言无关,但对于所有在Java中实现的人:不要重新发明轮子并使用Joda Time。

http://joda-time.sourceforge.net/api-release/org/joda/time/base/AbstractInterval.html#overlaps(org.joda.time.ReadableInterval


8
2017-10-13 15:10