给定两个日期范围,确定两个日期是否重叠的最简单或最有效的方法是什么?
例如,假设我们有由DateTime变量StartDate1到EndDate1和StartDate2到EndDate2表示的范围。
给定两个日期范围,确定两个日期是否重叠的最简单或最有效的方法是什么?
例如,假设我们有由DateTime变量StartDate1到EndDate1和StartDate2到EndDate2表示的范围。
当前回答
为了涵盖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的范围之间。
其余部分完全重叠,如其他答案所述。
其他回答
通过简单地确保一个范围在另一个范围之前或同时开始,可以大大简化基于范围之间的关系来检查大量条件的所有解决方案。如果需要,您可以在前面交换范围。
然后,如果第二个范围开始是:
小于或等于第一范围结束(如果包含范围,则包含开始时间和结束时间);或小于(如果范围包括开始,不包括结束)。
例如(假设两端都包含),范围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
其中每条线具有:
这两个范围被评估;“范围空间”(从最低开始到最高结束)的图形表示,其中每个字符都是“范围空间中的值”:'仅表示第一个范围内的值;,仅指示第二范围内的值;|表示两个范围中的值;和表示两个范围中的值。重叠检查的结果。
您可以非常清楚地看到,只有在两个范围中都至少有一个值(即,一个|字符)时,才能在重叠检查中获得真值。其他情况都是假的。
如果您想添加更多测试用例,请随意使用任何其他值。
我找到了另一个非常简单的方法。如果daterange1的开始和结束日期在daterange2的开始日期之前,或者daterange3的开始和终止日期在daterange2的结束日期之后,这意味着它们彼此不相交。
public boolean doesIntersect(DateRangeModel daterange1, DateRangeModel daterange2) {
return !(
(daterange1.getStartDate().isBefore(daterange2.getStartDate())
&& daterange1.getEndDate().isBefore(daterange2.getStartDate())) ||
(daterange1.getStartDate().isAfter(daterange2.getStartDate())
&& daterange1.getEndDate().isAfter(daterange2.getEndDate())));
}
此处发布的解决方案不适用于所有重叠范围。。。
----------------------|-------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. )
如果您使用的日期范围尚未结束(仍在进行中),例如未设置endDate='0000-00-00'您不能使用BETWEEN,因为0000-00-00不是有效日期!
我使用了这个解决方案:
(Startdate BETWEEN '".$startdate2."' AND '".$enddate2."') //overlap: starts between start2/end2
OR (Startdate < '".$startdate2."'
AND (enddate = '0000-00-00' OR enddate >= '".$startdate2."')
) //overlap: starts before start2 and enddate not set 0000-00-00 (still on going) or if enddate is set but higher then startdate2
如果startdate2高于enddate,则没有重叠!
@Bretana给出的数学解很好,但忽略了两个具体细节:
封闭或半开放间隔的方面空间隔
关于区间边界的封闭或开放状态,@Bretana的解对封闭区间有效
(起点A<=终点B)和(终点A>=起点B)
可以重写为半开间隔:
(开始A<结束B)和(结束A>开始B)
这种校正是必要的,因为根据定义,开放区间边界不属于区间的值范围。
关于空间隔,这里上面所示的关系不成立。根据定义不包含任何有效值的空间隔必须作为特殊情况处理。我通过Java时间库Time4J通过以下示例进行了演示:
MomentInterval a = MomentInterval.between(Instant.now(), Instant.now().plusSeconds(2));
MomentInterval b = a.collapse(); // make b an empty interval out of a
System.out.println(a); // [2017-04-10T05:28:11,909000000Z/2017-04-10T05:28:13,909000000Z)
System.out.println(b); // [2017-04-10T05:28:11,909000000Z/2017-04-10T05:28:11,909000000Z)
前导方括号“[”表示封闭的开始,而最后一个括号“)”表示开放的结束。
System.out.println(
"startA < endB: " + a.getStartAsInstant().isBefore(b.getEndAsInstant())); // false
System.out.println(
"endA > startB: " + a.getEndAsInstant().isAfter(b.getStartAsInstant())); // true
System.out.println("a overlaps b: " + a.intersects(b)); // a overlaps b: false
如上所示,空间隔违反了上面的重叠条件(尤其是startA<endB),因此Time4J(以及其他库)必须将其作为特殊的边缘情况来处理,以确保任何任意间隔与空间隔的重叠都不存在。当然,日期间隔(默认情况下在Time4J中是关闭的,但也可以是半开的,就像空日期间隔一样)的处理方式类似。