给定两个日期范围，确定这两个日期范围是否重叠的最简单或最有效的方法是什么？
例如，假设我们有由DateTime变量StartDate1到EndDate1和StartDate2到EndDate2表示的范围。
例如，假设我们有由DateTime变量StartDate1到EndDate1和StartDate2到EndDate2表示的范围。
确定两个日期范围是否重叠
1618
- Ian Nelson
9
3与https://dev59.com/C3VC5IYBdhLWcg3wZwTj极为相似。 - Charles Bretana
1@CharlesBretana 谢谢你，你说得对 - 那几乎就像是我问题的二维版本！ - Ian Nelson
2非常相似的问题: https://dev59.com/NnVD5IYBdhLWcg3wBWvd - Steven A. Lowe
2将“两个日期范围相交”的情况分为两种情况，然后对每种情况进行测试。 - Colonel Panic
1嗨.. A: StartDate1，B: EndDate1，C: StartDate2，D: EndDate2。如果 B < C 或 A > D，则我们假设它们不相交。因此，我们可以轻松地测试“isintersects = not (B < C or A > D)”，这将始终告诉我们它们是否相交。 - Nihat Erim inceoğlu
显示剩余4条评论
40个回答
2937
(StartA <= EndB) and (EndA >= StartB)
证明:
假设条件A表示时间段A完全在时间段B之后
_ |---- DateRange A ------|
|---Date Range B -----| _
如果StartA > EndB，则为真。
令条件B表示日期范围A完全在日期范围B之前。
|---- DateRange A -----| _
_ |---Date Range B ----|
(当且仅当 EndA < StartB 时为真)
如果既不满足 A 也不满足 B，则存在重叠 -（如果一个范围不完全在另一个范围之后，也不完全在另一个范围之前，则它们必须重叠）。
现在，德摩根定律（De Morgan's laws） 之一是：
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)。
这实际上是一个语法快捷方式，用于较长的实现中，其中包括额外的检查以验证开始日期是否在截止日期之前或同一天。从上面推导出来的结果如下：
如果开始和结束日期可以无序，例如，如果可能出现 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) ? StartA : StartB) <= ((EndA < EndB) ? EndA : EndB)
- Charles Bretana
15
59这是基于以下两个假设的简化逻辑：1）StartA < EndA；2）StartB < EndB。这似乎很明显，但实际上，数据可能来自未知来源，例如用户输入或未经消毒的数据库。请记住，在使用此简化逻辑之前，您需要验证输入数据以确保这两个假设为真，否则一切都会崩溃。从我的经验中吸取教训 ;) - Devy
15@Devy，你是正确的。除此之外，如果 startA = endA，它也可以工作。实际上，这正是“开始”和“结束”这两个词的意思。如果你有两个变量名分别为Top和Bottom、East和West、HighValue和LoValue，那么可以假定或暗示某个事物或某个人确保不将一对值存储在相反的变量中。只有其中一个对值，因为如果交换了两对值，它也能够正常工作。 - Charles Bretana
29您可以很容易地添加可为空的
start 和 end 参数（其含义为“空起始”等价于“从时间开始”，而“空结束”等价于“到时间结束”），方法如下：(startA === null || endB === null || startA <= endB) && (endA === null || startB === null || endA >= startB)。 - Kevin Robatel8这是我在StackOverflow上看到的最佳答案。 - Sampath
显示剩余10条评论
538
我相信只需要说两个范围重叠当:
(StartDate1 <= EndDate2) and (StartDate2 <= EndDate1)
- Ian Nelson
6
110我认为
(StartDate1 <= EndDate2) and (EndDate1 >= StartDate2) 这种表示法更易于理解，测试中 Range1 始终在左侧。 - A.L18假设起始日期和结束日期都是包含的。 如果起始日期包含在内，而结束日期不包含在内，请将“<=”更改为“<”。 - Richard Schneider
即使startDate2在startDate1之前，这也可以很好地工作。因此不需要假设startDate1早于startDate2。 - Shehan Simen
3根据答案，我发现(StartDate1 <= EndDate2) and (StartDate2 <= EndDate1) 表达方式更易于理解，比其他答案中的表达方式更为简单明了。 - apc
如何使其适用于具有 StartDate1 和 / 或 EndDate1 的数据？
该代码假定 StartDate1 和 EndDate1 始终存在。如果只给出 StartDate1 而没有 EndDate1，或者只给出 EndDate1 而没有 StartDate1，该怎么处理这种额外情况？ - juFo
如何使起始值独占，而结束值包含在内？ - Jay Patel
169
本文.NET时间周期库描述了通过枚举PeriodRelation来确定两个时间周期之间的关系：
// ------------------------------------------------------------------------
public enum PeriodRelation
{
After,
StartTouching,
StartInside,
InsideStartTouching,
EnclosingStartTouching,
Enclosing,
EnclosingEndTouching,
ExactMatch,
Inside,
InsideEndTouching,
EndInside,
EndTouching,
Before,
} // enum PeriodRelation
- user687474
2
4撰写重叠日期规格说明的好方法总结。 - ToTenMilan
104
为了推理时间关系（或任何其他间隔关系），可以考虑Allen's Interval Algebra。它描述了两个间隔相互之间可能存在的13种关系。你可以找到其他参考资料-“Allen Interval”似乎是一个有效的搜索词。您还可以在Snodgrass的Developing Time-Oriented Applications in SQL（可在URL上在线获取PDF）以及Date，Darwen和Lorentzos的Temporal Data and the Relational Model（2002年）或Time and Relational Theory: Temporal Databases in the Relational Model and SQL（2014年；实际上是TD&RM的第二版）中了解有关这些操作的信息。
简短的答案是：给定两个日期区间A和B，具有组件.start和.end以及约束条件.start <= .end，则当：
A.end >= B.start AND A.start <= B.end
您可以调整使用 >= vs > 和 <= vs < 来满足您对重叠程度的要求。
ErikE评论：
如果你愿意拧巴一些，你只能得到13...但是当我有点发疯的时候，我可以得到"两个区间之间可能存在15种关系"。通过合理的计算，我只得到了六种，并且如果不考虑A或B先出现的顺序，我只得到了三种（不相交、部分相交、一个在另一个内部）。15种情况如下：[before:before, start, within, end, after]，[start:start, within, end, after]，[within:within, end, after]，[end:end, after]，[after:after]。
我认为您不能计算'before:before'和'after:after'这两项。如果您将某些关系与它们的反向关系等同起来（请参见参考Wikipedia URL中的图表），则可以看到7个条目；其中6个有不同的反向关系，而相等的没有单独的反向关系。至于三是否合理取决于您的要求。
----------------------|-------A-------|----------------------
|----B1----|
|----B2----|
|----B3----|
|----------B4----------|
|----------------B5----------------|
|----B6----|
----------------------|-------A-------|----------------------
|------B7-------|
|----------B8-----------|
|----B9----|
|----B10-----|
|--------B11--------|
|----B12----|
|----B13----|
----------------------|-------A-------|----------------------
- Jonathan Leffler
10
1只有你以奇怪的方式计算时才能得到13...当我疯狂地计算时，我可以得到“两个区间可能具有的15种关系”。通过合理的计数，我只得到了六个，如果不考虑A或B先出现的顺序，我只得到了三个（没有相交，部分相交，一个完全在另一个内）。15种情况如下：
[before:before, start, within, end, after], [start:start, within, end, after],[within:within, end, after], [end:end, after], [after:after]。 - ErikE
关于您的更新：B1到A是before:before，B13到A是after:after。您漂亮的图表中缺少了B5 B6之间的start:start和B11和B12之间的end:end。如果在端点上很重要，则必须计算它，因此最终总数为15，而不是13。我*不认为端点的事情很重要，所以我个人认为它是[before:before, within, after]，[within:within, after]，[after:after]，共6个。我认为整个端点的事情只是关于边界是包含还是排除的混淆。端点的排除并不改变核心关系！ - ErikE
在与乔纳森的电子邮件交流后，我意识到在我的模型中，开始时间是包含的，结束时间是排除的，一个以相同时间开始和停止的范围长度为零（因为它在开始之前就结束了）。因此，在我的方案中[start:start]和[end:end]没有意义。然而，乔纳森建议的方案要求端点是包含的，否则B2和A（例如）的范围将不相交。对我来说，这是有问题的，因为计算机中的时间并非表示为无限精度。请参见下一条评论-> - ErikE
如果结束时间是包含的，则为了表示计算机中不重叠但连续的范围，必须从较早段的结束时间中减去允许的最小时间增量。例如，在具有datetime数据类型的SQL Server中，范围A：'20100101 09:00' - '20100101 10:00'和B：'20100101 10:00' - '20100101 11:00'将重叠1/300毫秒。为使它们连续且不重叠，第一个范围必须调整为A：'20100101 09:00' - '20100101 09:59:59.997'。但出于多种原因，这是完全不可接受的（下一页->）。 - ErikE
第一個且不太重要的原因是人們不會這樣想時間。他們想說範圍從9開始，到10結束。如果您正在從用戶收集數據，那麼您必須呈現09:59:59.997垃圾數據（這永遠不起作用），或者在存儲它們時調整所有時間（也沒有更好）。第二個且更重要的原因是基礎數據類型不應更改數據的業務含義。如果日期時間列轉換為具有00:00:00到23:59:59.9999999的datetime2（http://technet.microsoft.com/en-us/library/bb677335.aspx），會怎麼樣？ - ErikE
显示剩余5条评论
40
如果需要计算重叠部分，您可以使用以下公式：
overlap = max(0, min(EndDate1, EndDate2) - max(StartDate1, StartDate2))
if (overlap > 0) {
...
}
- Vitalii Fedorenko
2
所以重叠是两个事件共享的时间量？这适用于所有不同的事件重叠方式吗？ - NSjonas
2当存在完全重叠时，这种方法无法正常工作。例如：范围1：1-7 范围2：4-5 - Kakshil Shah
23
所有基于范围相对位置检查多种条件的解决方案，都可以通过确保一个范围在另一个范围之前或同时开始来大大简化。如果需要，您可以事先交换范围。
然后，您可以检测重叠区域是否存在，如果第二个范围的开始时间：
如果范围在末尾是“排除的”，则您只需在返回的表达式中用“<”替换“<=”（在两个代码段中都要这样做），这将大大减少您需要进行的检查数量，因为您通过确保第一个范围从未在第二个范围之后开始而提前删除了问题空间的一半。
由于“代码说话”，因此这里有一些Python代码，展示了它的作用，并包含相当多的测试用例。首先是“InclusiveRange”类:
运行后会产生以下输出：
然后，您可以检测重叠区域是否存在，如果第二个范围的开始时间：
- 小于或等于第一个范围的结束时间（如果范围包含开始和结束时间）；或者
- 小于第一个范围的结束时间（如果范围包括开始但不包括结束时间）。
>表示范围结束位置不影响）。|-----| 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
每行内容包括：
- 两个被评估的范围；
- "范围空间"的图形表示（从最低起始到最高结束），其中每个字符都是该"范围空间"中的一个值：
'表示仅在第一个范围内的值；,表示仅在第二个范围内的值；|表示在两个范围内的值；
- 重叠检查的结果。
很明显，只有当至少有一个值在两个范围中时（即，一个|字符），您才会在重叠检查中得到true。其他情况均为false。
如果您想添加更多测试用例，请随意使用任何其他值。
- paxdiablo
1
2+1 提到了包含/不包含的问题。我本来打算等有时间时自己回答，但现在没必要了。事实上，你几乎从不允许同时包含起始和结束。在我的行业中，通常将起始视为排除，将结束视为包含，但只要保持一致，任何方式都可以。这是迄今为止对这个问题的第一个完全正确的答案...在我看来。 - Brian Gideon
20
这里是另一种使用JavaScript的解决方案。我的解决方案的特点：
- 将null值处理为无穷大
- 假定下限包含，上限不包含。
- 附带了一些测试
这些测试基于整数，但由于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项测试，全部通过，用时0.003秒/总计0.004秒。
- yankee
17
这里是实现魔法的代码：
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结束
证明？请查看此测试控制台代码要点。
- sandeep talabathula
5
那是有效的，但我更喜欢测试非重叠情况，只有两种可能性。 - John Albert
1谢谢您使用图片来解释。您的答案是这个问题的完美解决方案。 - Rakesh Verma
1由于按定义，A始终小于等于B且C始终小于等于D，因此可以简化为(A <= D) && (C <= B)。 - Manuel Romeiro
@ManuelRomeiro 你好，如果2Start < 1Start且2End > 1End，它会起作用吗？ - ITSagar
@sandeep talabathula 你好，如果2Start < 1Start且2End > 1End的情况下，它能正常工作吗？ - ITSagar
13
记住解决方法的简单方式是min(ends)>max(starts)
- Radacina
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));
}
- Khaled.K
6
我认为你想说的是无界端而不是开区间。 - Henrik
@Henrik 两个术语都可以使用 https://en.wikipedia.org/wiki/Interval_(mathematics)#Terminology - Khaled.K
!startA.after(endB) 表示 startA <= endB，而 !endA.before(startB) 表示 startB <= endA。这些是闭区间的标准，而不是开区间。 - Henrik@Henrik 确实如此，而且其他条件如
endB == null 和 startA == null 则是用来检查开放区间的。 - Khaled.K1
endB == null, startA == null, endA == null 和 startB == null 都是检查无界区间而不是开放区间的标准。例如，(10, 20) 和 (20, null) 是两个不重叠的开放区间。后者具有无限的结尾。您的函数将返回 true，但是这些区间不重叠，因为这些区间不包括 20。 （为简单起见使用数字而不是时间戳） - Henrik@Henrik 我明白了，我已经修复好了。 - Khaled.K
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接