本文共 20787 字,大约阅读时间需要 69 分钟。
给定两个日期范围,确定两个日期范围是否重叠的最简单或最有效的方法是什么?
例如,假设我们有一个用变量StartDate1
到EndDate1
以及 StartDate2
到EndDate2
表示的范围。
如果还应该计算重叠本身,则可以使用以下公式:
overlap = max(0, min(EndDate1, EndDate2) - max(StartDate1, StartDate2))if (overlap > 0) { ...}
将问题分成案例然后处理每个案例 。
“两个日期范围相交”的情况有两种情况-第一个日期范围在第二个日期范围内开始,或者第二个日期范围在第一个日期范围内开始。
这是我的moment.js的javascript解决方案:
// Current row datesvar dateStart = moment("2014-08-01", "YYYY-MM-DD");var dateEnd = moment("2014-08-30", "YYYY-MM-DD");// Check with dates abovevar 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 goodreturn true;
此处发布的解决方案不适用于所有重叠范围...
----------------------|-------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.)
您可以尝试以下方法:
//custom date for example$d1 = new DateTime("2012-07-08");$d2 = new DateTime("2012-07-11");$d3 = new DateTime("2012-07-08");$d4 = new DateTime("2012-07-15");//create a date period object$interval = new DateInterval('P1D');$daterange = iterator_to_array(new DatePeriod($d1, $interval, $d2));$daterange1 = iterator_to_array(new DatePeriod($d3, $interval, $d4));array_map(function($v) use ($daterange1) { if(in_array($v, $daterange1)) print "Bingo!";}, $daterange);
如果您使用的日期范围尚未结束(仍在进行中),例如未设置endDate ='0000-00-00',则不能使用BETWEEN,因为0000-00-00不是有效的日期!
我使用了以下解决方案:
(Startdate BETWEEN '".$startdate2."' AND '".$enddate2."') //overlap: starts between start2/end2OR (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没有重叠!
在Microsoft SQL SERVER中-SQL函数
CREATE FUNCTION IsOverlapDates ( @startDate1 as datetime, @endDate1 as datetime, @startDate2 as datetime, @endDate2 as datetime)RETURNS intASBEGINDECLARE @Overlap as intSET @Overlap = (SELECT CASE WHEN ( (@startDate1 BETWEEN @startDate2 AND @endDate2) -- caters for inner and end date outer OR (@endDate1 BETWEEN @startDate2 AND @endDate2) -- caters for inner and start date outer OR (@startDate2 BETWEEN @startDate1 AND @endDate1) -- only one needed for outer range where dates are inside. ) THEN 1 ELSE 0 END ) RETURN @OverlapENDGO--Execution of the above codeDECLARE @startDate1 as datetimeDECLARE @endDate1 as datetimeDECLARE @startDate2 as datetimeDECLARE @endDate2 as datetimeDECLARE @Overlap as intSET @startDate1 = '2014-06-01 01:00:00' SET @endDate1 = '2014-06-01 02:00:00'SET @startDate2 = '2014-06-01 01:00:00' SET @endDate2 = '2014-06-01 01:30:00'SET @Overlap = [dbo].[IsOverlapDates] (@startDate1, @endDate1, @startDate2, @endDate2)SELECT Overlap = @Overlap
public static class NumberExtensionMethods { public static Boolean IsBetween(this Int64 value, Int64 Min, Int64 Max) { if (value >= Min && value <= Max) return true; else return false; } public static Boolean IsBetween(this DateTime value, DateTime Min, DateTime Max) { Int64 numricValue = value.Ticks; Int64 numericStartDate = Min.Ticks; Int64 numericEndDate = Max.Ticks; if (numricValue.IsBetween(numericStartDate, numericEndDate) ) { return true; } return false; } }public static Boolean IsOverlap(DateTime startDate1, DateTime endDate1, DateTime startDate2, DateTime endDate2) { Int64 numericStartDate1 = startDate1.Ticks; Int64 numericEndDate1 = endDate1.Ticks; Int64 numericStartDate2 = startDate2.Ticks; Int64 numericEndDate2 = endDate2.Ticks; if (numericStartDate2.IsBetween(numericStartDate1, numericEndDate1) || numericEndDate2.IsBetween(numericStartDate1, numericEndDate1) || numericStartDate1.IsBetween(numericStartDate2, numericEndDate2) || numericEndDate1.IsBetween(numericStartDate2, numericEndDate2)) { return true; } return false; } if (IsOverlap(startdate1, enddate1, startdate2, enddate2)) { Console.WriteLine("IsOverlap"); }
这是我的解决方案,当值不重叠时返回true:
X START 1 Y END 1
A START 2 B END 2
TEST1: (X <= A || X >= B) &&TEST2: (Y >= B || Y <= A) && TEST3: (X >= B || Y <= A)X-------------Y A-----BTEST1: TRUETEST2: TRUETEST3: FALSERESULT: FALSE---------------------------------------X---Y A---BTEST1: TRUETEST2: TRUETEST3: TRUERESULT: TRUE--------------------------------------- X---YA---BTEST1: TRUETEST2: TRUETEST3: TRUERESULT: TRUE--------------------------------------- X----YA---------------BTEST1: FALSETEST2: FALSETEST3: FALSERESULT: FALSE
使用Java util.Date,这就是我所做的。
public static boolean checkTimeOverlaps(Date startDate1, Date endDate1, Date startDate2, Date endDate2) { if (startDate1 == null || endDate1 == null || startDate2 == null || endDate2 == null) return false; if ((startDate1.getTime() <= endDate2.getTime()) && (startDate2.getTime() <= endDate1.getTime())) return true; return false; }
这是使用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 <= EndDate2) and (StartDate2 <= EndDate1)
我会做
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); }
我认为最简单的方法是比较EndDate1是否在StartDate2之前,而EndDate2在StartDate1之前。
当然,如果您考虑的间隔是StartDate始终位于EndDate之前。
(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都不为真,则存在重叠-
(如果一个范围不完全在另一个范围之后, 也不完全在另一个之前,那么它们必须重叠。)现在, 一项 :
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()
,您必须进行编码(使用C三进制来简洁):
(StartA > StartB? Start A: StartB) <= (EndA < EndB? EndA: EndB)
对于时间关系(或其他任何区间关系)的推理,请考虑 。 它描述了两个间隔相对于彼此可能具有的13种可能的关系。 您可以找到其他参考文献-“艾伦间隔”似乎是一个有效的搜索词。 您还可以在Snodgrass的找到有关这些操作的信息(可在URL上在线获取PDF),以及在Date,Darwen和Lorentzos的 (2002)或 (2014年;有效的TD&RM第二版)。
简短的答案是:给定两个日期间隔A
和B
,其成分为.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-------|----------------------
对于红宝石,我也发现了这一点:
class Interval < ActiveRecord::Base validates_presence_of :start_date, :end_date # Check if a given interval overlaps this interval def overlaps?(other) (start_date - other.end_date) * (other.start_date - end_date) >= 0 end # Return a scope for all interval overlapping the given interval, including the given interval itself named_scope :overlapping, lambda { |interval| { :conditions => ["id <> ? AND (DATEDIFF(start_date, ?) * DATEDIFF(?, end_date)) >= 0", interval.id, interval.end_date, interval.start_date] }}end
在这里找到了很好的解释->
仅通过确保特定范围开始得较早,就可以大大简化基于范围之间的相对位置检查多种条件的所有解决方案! 您可以通过在必要时预先交换范围来确保第一个范围更早(或同时)开始。
然后,如果另一个范围起点小于或等于第一个范围终点(如果范围包括两端,都包含开始和结束时间)或小于(如果范围包括起点并且不包括终点),则可以检测到重叠。
假设两端都具有包容性,则只有四种可能性,其中一种是非重叠的:
|----------------------| 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之后永远不会开始,可以尽早消除问题空间的一半。
最简单的
最简单的方法是使用精心设计的专用库进行日期时间工作。
someInterval.overlaps( anotherInterval )
最好的业务是内置在Java 8及更高版本中的框架。 添加到项目中,该项目用其他类(特别是我们在这里需要的类)补充java.time。
至于此课题上与标记,两个项目的源代码都可以用其他语言使用(请注意其许可)。
Interval
类很方便,但是需要日期时间点( java.time.Instant
对象),而不是仅日期值。 因此,我们使用UTC中的第一天来代表日期。
Instant start = Instant.parse( "2016-01-01T00:00:00Z" );Instant stop = Instant.parse( "2016-02-01T00:00:00Z" );
创建一个Interval
以表示该时间跨度。
Interval interval_A = Interval.of( start , stop );
我们还可以定义一个带有开始时间加上 Interval
。
Instant start_B = Instant.parse( "2016-01-03T00:00:00Z" );Interval interval_B = Interval.of( start_B , Duration.of( 3 , ChronoUnit.DAYS ) );
比较测试是否容易。
Boolean overlaps = interval_A.overlaps( interval_B );
您可以将一个与另一个或 :
所有这些方法都使用Half-Open
方法来定义一个时间范围,其中开始是包含在内的 ,结束是排斥的 。
答案对我来说太简单了,所以我创建了一个更通用的动态SQL语句,该语句检查一个人是否有重叠的日期。
SELECT DISTINCT T1.EmpIDFROM Table1 T1INNER JOIN Table2 T2 ON T1.EmpID = T2.EmpID AND T1.JobID <> T2.JobID AND ( (T1.DateFrom >= T2.DateFrom AND T1.dateFrom <= T2.DateTo) OR (T1.DateTo >= T2.DateFrom AND T1.DateTo <= T2.DateTo) OR (T1.DateFrom < T2.DateFrom AND T1.DateTo IS NULL) ) AND NOT (T1.DateFrom = T2.DateFrom)
我遇到的情况是我们有日期而不是日期时间,并且日期只能在开始/结束时重叠。 下面的例子:
(绿色是当前间隔,蓝色是有效间隔,红色是重叠间隔)。
我将Ian Nelson的答案改编为以下解决方案:
(startB <= startA && endB > startA)|| (startB >= startA && startB < endA)
这会匹配所有重叠的情况,但会忽略允许的重叠情况。
这是我在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));}
@Bretana给出的数学解决方案很好,但忽略了两个具体细节:
关于区间边界的闭合或打开状态,@ Bretana的解对于闭合区间有效
(StartA <= EndB)和(EndA> = StartB)
可以半开时间间隔重写为 :
(StartA <EndB)和(EndA> StartB)
由于定义上开放区间边界不属于区间的值范围,因此必须进行校正。
关于空间隔 ,那么,上面显示的关系不成立。 根据定义,不包含任何有效值的空间隔必须作为特殊情况处理。 我通过以下示例通过Java时间库进行了演示:
MomentInterval a = MomentInterval.between(Instant.now(), Instant.now().plusSeconds(2));MomentInterval b = a.collapse(); // make b an empty interval out of aSystem.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())); // falseSystem.out.println( "endA > startB: " + a.getEndAsInstant().isAfter(b.getStartAsInstant())); // trueSystem.out.println("a overlaps b: " + a.intersects(b)); // a overlaps b: false
如上所示,空间隔违反了上面的重叠条件(尤其是startA <endB),因此,Time4J(以及其他库)也必须将其作为特殊的边缘情况进行处理,以确保任意间隔与空间隔的重叠不存在。 当然,日期间隔(在Time4J中默认关闭,但也可以半开,如空的日期间隔)的处理方式也类似。
这是@ 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 ----]
重叠iff: (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 ----)
重叠iff: (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)
等等...
最后,两个间隔重叠的一般条件是
(StartA <🞐EndB)和(EndA>🞐StartB)
其中,每当在两个包含的端点之间进行比较时,🞐就会将严格的不等式变成非严格的不等式。
这是执行魔术的代码:
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));
哪里..
证明? 查看此测试 。
这是另一个使用momentjs的简短答案:
function isOverlapping(startDate1, endDate1, startDate2, endDate2){ return moment(startDate1).isSameOrBefore(endDate2) && moment(startDate2).isSameOrBefore(endDate1);}
答案是基于以上答案,但它有所缩短。
一个容易记住的解决方案是
min(ends)>max(starts)
本文时间段库通过枚举PeriodRelation描述了两个时间段的关系:
// ------------------------------------------------------------------------public enum PeriodRelation{ After, StartTouching, StartInside, InsideStartTouching, EnclosingStartTouching, Enclosing, EnclosingEndTouching, ExactMatch, Inside, InsideEndTouching, EndInside, EndTouching, Before,} // enum PeriodRelation
这是可以在本地使用的通用方法。
// Takes a list and returns all records that have overlapping time ranges. public static IEnumerableGetOverlappedTimes (IEnumerable list, Func filter, Func start, Func end) { // Selects all records that match filter() on left side and returns all records on right side that overlap. var overlap = from t1 in list where filter(t1) from t2 in list where !object.Equals(t1, t2) // Don't match the same record on right side. let in1 = start(t1) let out1 = end(t1) let in2 = start(t2) let out2 = end(t2) where in1 <= out2 && out1 >= in2 let totover = GetMins(in1, out1, in2, out2) select t2; return overlap; } public static void TestOverlap() { var tl1 = new TempTimeEntry() { ID = 1, Name = "Bill", In = "1/1/08 1:00pm".ToDate(), Out = "1/1/08 4:00pm".ToDate() }; var tl2 = new TempTimeEntry() { ID = 2, Name = "John", In = "1/1/08 5:00pm".ToDate(), Out = "1/1/08 6:00pm".ToDate() }; var tl3 = new TempTimeEntry() { ID = 3, Name = "Lisa", In = "1/1/08 7:00pm".ToDate(), Out = "1/1/08 9:00pm".ToDate() }; var tl4 = new TempTimeEntry() { ID = 4, Name = "Joe", In = "1/1/08 3:00pm".ToDate(), Out = "1/1/08 8:00pm".ToDate() }; var tl5 = new TempTimeEntry() { ID = 1, Name = "Bill", In = "1/1/08 8:01pm".ToDate(), Out = "1/1/08 8:00pm".ToDate() }; var list = new List () { tl1, tl2, tl3, tl4, tl5 }; var overlap = GetOverlappedTimes(list, (TempTimeEntry t1)=>t1.ID==1, (TempTimeEntry tIn) => tIn.In, (TempTimeEntry tOut) => tOut.Out); Console.WriteLine("\nRecords overlap:"); foreach (var tl in overlap) Console.WriteLine("Name:{0} T1In:{1} T1Out:{2}", tl.Name, tl.In, tl.Out); Console.WriteLine("Done"); /* Output: Records overlap: Name:Joe T1In:1/1/2008 3:00:00 PM T1Out:1/1/2008 8:00:00 PM Name:Lisa T1In:1/1/2008 7:00:00 PM T1Out:1/1/2008 9:00:00 PM Done */ }
if (StartDate1 > StartDate2) swap(StartDate, EndDate);(StartDate1 <= EndDate2) and (StartDate2 <= EndDate1);
转载地址:http://wxogj.baihongyu.com/