检测重叠周期的algorithm

我必须检测两个时间段是否重叠。

每个时期都有开始date和结束date。

我需要检测我的第一个时间段（A）是否与另一个（B / C）重叠。

在我的情况下，如果B的开始等于A的结束，它们不重叠（也是相反的）

我发现以下情况：

所以其实我是这样做的：

tStartA < tStartB && tStartB < tEndA //For case 1 OR tStartA < tEndB && tEndB <= tEndA //For case 2 OR tStartB < tStartA && tEndB > tEndA //For case 3 

（在案例1或案例2中考虑了案例4）

它工作 ，但似乎不是很有效。

所以，首先是在c＃中有一个现有的类，可以模拟这个（时间段），像时间安排，但有一个固定的开始date。

其次：是否已经有ac＃代码（就像在Datetime类中）可以处理这个？

第三：如果不是的话，你会怎么做这个比较最快？

Answer 1

简单检查两个时间段是否重叠：

 bool overlap = a.start < b.end && b.start < a.end; 

或者在你的代码中：

 bool overlap = tStartA < tEndB && tStartB < tEndA; 

（如果你改变主意，想要说两个彼此接触的时期重叠，请使用<=而不是< ）。

Answer 2

在CodeProject上有一个很好的评论库： http : //www.codeproject.com/Articles/168662/Time-Period-Library-for-NET

这个库在重叠，交叉等方面做了很多工作。复制/粘贴所有内容太大了，但是我会看到哪些特定的部分对你有用。

Answer 3

你可以创build一个可重复使用的Range模式类：

 public class Range<T> where T : IComparable { readonly T min; readonly T max; public Range(T min, T max) { this.min = min; this.max = max; } public bool IsOverlapped(Range<T> other) { return Min.CompareTo(other.Max) < 0 && other.Min.CompareTo(Max) < 0; } public T Min { get { return min; } } public T Max { get { return max; } } } 

您可以添加所需的所有方法来合并范围，获得交点等…

Answer 4

我正在build立订票系统，并find了这个页面。 我只对范围交叉感兴趣，所以我build立了这个结构; 使用DateTime范围就足够了。

您可以检查交叉口，并检查特定date是否在范围内，并获取交叉口types，最重要的是：您可以得到相交的范围。

 public struct DateTimeRange { #region Construction public DateTimeRange(DateTime start, DateTime end) { if (start>end) { throw new Exception("Invalid range edges."); } _Start = start; _End = end; } #endregion #region Properties private DateTime _Start; public DateTime Start { get { return _Start; } private set { _Start = value; } } private DateTime _End; public DateTime End { get { return _End; } private set { _End = value; } } #endregion #region Operators public static bool operator ==(DateTimeRange range1, DateTimeRange range2) { return range1.Equals(range2); } public static bool operator !=(DateTimeRange range1, DateTimeRange range2) { return !(range1 == range2); } public override bool Equals(object obj) { if (obj is DateTimeRange) { var range1 = this; var range2 = (DateTimeRange)obj; return range1.Start == range2.Start && range1.End == range2.End; } return base.Equals(obj); } public override int GetHashCode() { return base.GetHashCode(); } #endregion #region Querying public bool Intersects(DateTimeRange range) { var type = GetIntersectionType(range); return type != IntersectionType.None; } public bool IsInRange(DateTime date) { return (date >= this.Start) && (date <= this.End); } public IntersectionType GetIntersectionType(DateTimeRange range) { if (this == range) { return IntersectionType.RangesEqauled; } else if (IsInRange(range.Start) && IsInRange(range.End)) { return IntersectionType.ContainedInRange; } else if (IsInRange(range.Start)) { return IntersectionType.StartsInRange; } else if (IsInRange(range.End)) { return IntersectionType.EndsInRange; } else if (range.IsInRange(this.Start) && range.IsInRange(this.End)) { return IntersectionType.ContainsRange; } return IntersectionType.None; } public DateTimeRange GetIntersection(DateTimeRange range) { var type = this.GetIntersectionType(range); if (type == IntersectionType.RangesEqauled || type==IntersectionType.ContainedInRange) { return range; } else if (type == IntersectionType.StartsInRange) { return new DateTimeRange(range.Start, this.End); } else if (type == IntersectionType.EndsInRange) { return new DateTimeRange(this.Start, range.End); } else if (type == IntersectionType.ContainsRange) { return this; } else { return default(DateTimeRange); } } #endregion public override string ToString() { return Start.ToString() + " - " + End.ToString(); } } public enum IntersectionType { /// <summary> /// No Intersection /// </summary> None = -1, /// <summary> /// Given range ends inside the range /// </summary> EndsInRange, /// <summary> /// Given range starts inside the range /// </summary> StartsInRange, /// <summary> /// Both ranges are equaled /// </summary> RangesEqauled, /// <summary> /// Given range contained in the range /// </summary> ContainedInRange, /// <summary> /// Given range contains the range /// </summary> ContainsRange, } 

Answer 5

如何定制间隔树结构？ 您必须稍微调整一下，以定义两个区间在您的域中“重叠”的含义。

这个问题可能会帮助你在C＃中find一个现成的间隔树实现。

Answer 6

我不相信框架本身有这个类。 也许是第三方库…

但为什么不创build一个Period值对象类来处理这种复杂性呢？ 这样你就可以确保其他约束，比如validation开始和结束date。 就像是：

 using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace Whatever.Domain.Timing { public class Period { public DateTime StartDateTime {get; private set;} public DateTime EndDateTime {get; private set;} public Period(DateTime StartDateTime, DateTime EndDateTime) { if (StartDateTime > EndDateTime) throw new InvalidPeriodException("End DateTime Must Be Greater Than Start DateTime!"); this.StartDateTime = StartDateTime; this.EndDateTime = EndDateTime; } public bool Overlaps(Period anotherPeriod){ return (this.StartDateTime < anotherPeriod.EndDateTime && anotherPeriod.StartDateTime < this.EndDateTime) } public TimeSpan GetDuration(){ return EndDateTime - StartDateTime; } } public class InvalidPeriodException : Exception { public InvalidPeriodException(string Message) : base(Message) { } } } 

这样你就可以单独比较每个时期…

Answer 7

这段代码检查两个区间是否重叠。

 ---------|---| ---|---| > FALSE xxxxxxxxxxxxxxxxxxxxxxxxx -------|---| ---|---| > FALSE xxxxxxxxxxxxxxxxxxxxxxxxx ------|---| ---|---| > TRUE xxxxxxxxxxxxxxxxxxxxxxxxx ---|---| ---|--| > TRUE xxxxxxxxxxxxxxxxxxxxxxxxx ----|---| ---|-----| > TRUE xxxxxxxxxxxxxxxxxxxxxxxxx ---|---| ----|-| > TRUE xxxxxxxxxxxxxxxxxxxxxxxxx ---|---| ----|--| > TRUE xxxxxxxxxxxxxxxxxxxxxxxxx ---|---| ---|---| > TRUE xxxxxxxxxxxxxxxxxxxxxxxxx ---|---| ----|---| > TRUE xxxxxxxxxxxxxxxxxxxxxxxxx ---|---| -------|---| > TRUE xxxxxxxxxxxxxxxxxxxxxxxxx ---|---| --------|---| > TRUE 

algorithm：

 x1 < y2 and x2 > y1 

例如12:00 – 12:30与12:30 13:00不重叠

Answer 8

 --logic FOR OVERLAPPING DATES DECLARE @StartDate datetime --Reference start date DECLARE @EndDate datetime --Reference end date DECLARE @NewStartDate datetime --New Start date DECLARE @NewEndDate datetime --New End Date Select (Case when @StartDate is null then @NewStartDate when (@StartDate<@NewStartDate and @EndDate < @NewStartDate) then @NewStartDate when (@StartDate<@NewStartDate and @EndDate > @NewEndDate) then @NewStartDate when (@StartDate<@NewStartDate and @EndDate > @NewStartDate) then @NewStartDate when (@StartDate>@NewStartDate and @NewEndDate < @StartDate) then @NewStartDate else @StartDate end) as StartDate, (Case when @EndDate is null then @NewEndDate when (@EndDate>@NewEndDate and @Startdate < @NewEndDate) then @NewEndDate when (@EndDate>@NewEndDate and @Startdate > @NewEndDate) then @NewEndDate when (@EndDate<@NewEndDate and @NewStartDate > @EndDate) then @NewEndDate else @EndDate end) as EndDate 

分配逻辑

Answer 9

 public class ConcreteClassModel : BaseModel { ... rest of class public bool InersectsWith(ConcreteClassModel crm) { return !(this.StartDateDT > crm.EndDateDT || this.EndDateDT < crm.StartDateDT); } } [TestClass] public class ConcreteClassTest { [TestMethod] public void TestConcreteClass_IntersectsWith() { var sutPeriod = new ConcreteClassModel() { StartDateDT = new DateTime(2016, 02, 01), EndDateDT = new DateTime(2016, 02, 29) }; var periodBeforeSutPeriod = new ConcreteClassModel() { StartDateDT = new DateTime(2016, 01, 01), EndDateDT = new DateTime(2016, 01, 31) }; var periodWithEndInsideSutPeriod = new ConcreteClassModel() { StartDateDT = new DateTime(2016, 01, 10), EndDateDT = new DateTime(2016, 02, 10) }; var periodSameAsSutPeriod = new ConcreteClassModel() { StartDateDT = new DateTime(2016, 02, 01), EndDateDT = new DateTime(2016, 02, 29) }; var periodWithEndDaySameAsStartDaySutPeriod = new ConcreteClassModel() { StartDateDT = new DateTime(2016, 01, 01), EndDateDT = new DateTime(2016, 02, 01) }; var periodWithStartDaySameAsEndDaySutPeriod = new ConcreteClassModel() { StartDateDT = new DateTime(2016, 02, 29), EndDateDT = new DateTime(2016, 03, 31) }; var periodEnclosingSutPeriod = new ConcreteClassModel() { StartDateDT = new DateTime(2016, 01, 01), EndDateDT = new DateTime(2016, 03, 31) }; var periodWithinSutPeriod = new ConcreteClassModel() { StartDateDT = new DateTime(2016, 02, 010), EndDateDT = new DateTime(2016, 02, 20) }; var periodWithStartInsideSutPeriod = new ConcreteClassModel() { StartDateDT = new DateTime(2016, 02, 10), EndDateDT = new DateTime(2016, 03, 10) }; var periodAfterSutPeriod = new ConcreteClassModel() { StartDateDT = new DateTime(2016, 03, 01), EndDateDT = new DateTime(2016, 03, 31) }; Assert.IsFalse(sutPeriod.InersectsWith(periodBeforeSutPeriod), "sutPeriod.InersectsWith(periodBeforeSutPeriod) should be false"); Assert.IsTrue(sutPeriod.InersectsWith(periodWithEndInsideSutPeriod), "sutPeriod.InersectsWith(periodEndInsideSutPeriod)should be true"); Assert.IsTrue(sutPeriod.InersectsWith(periodSameAsSutPeriod), "sutPeriod.InersectsWith(periodSameAsSutPeriod) should be true"); Assert.IsTrue(sutPeriod.InersectsWith(periodWithEndDaySameAsStartDaySutPeriod), "sutPeriod.InersectsWith(periodWithEndDaySameAsStartDaySutPeriod) should be true"); Assert.IsTrue(sutPeriod.InersectsWith(periodWithStartDaySameAsEndDaySutPeriod), "sutPeriod.InersectsWith(periodWithStartDaySameAsEndDaySutPeriod) should be true"); Assert.IsTrue(sutPeriod.InersectsWith(periodEnclosingSutPeriod), "sutPeriod.InersectsWith(periodEnclosingSutPeriod) should be true"); Assert.IsTrue(sutPeriod.InersectsWith(periodWithinSutPeriod), "sutPeriod.InersectsWith(periodWithinSutPeriod) should be true"); Assert.IsTrue(sutPeriod.InersectsWith(periodWithStartInsideSutPeriod), "sutPeriod.InersectsWith(periodStartInsideSutPeriod) should be true"); Assert.IsFalse(sutPeriod.InersectsWith(periodAfterSutPeriod), "sutPeriod.InersectsWith(periodAfterSutPeriod) should be false"); } } 

感谢上面的答案，这有助于我为MVC项目编写上述代码。

注意StartDateDT和EndDateDT是dateTimetypes

Answer 10

尝试这个。 此方法将确定（两个）date跨度是否重叠，而不考虑方法的input参数的顺序。 这也可以用于两个以上的date跨度，通过单独检查每个date跨度组合（例如3个date跨度，运行span1对span2 ， span2对span3和span1对span3 ）：

 public static class HelperFunctions { public static bool AreSpansOverlapping(Tuple<DateTime,DateTime> span1, Tuple<DateTime,DateTime> span2, bool includeEndPoints) { if (span1 == null || span2 == null) { return false; } else if ((new DateTime[] { span1.Item1, span1.Item2, span2.Item1, span2.Item2 }).Any(v => v == DateTime.MinValue)) { return false; } else { if (span1.Item1 > span1.Item2) { span1 = new Tuple<DateTime, DateTime>(span1.Item2, span1.Item1); } if (span2.Item1 > span2.Item2) { span2 = new Tuple<DateTime, DateTime>(span2.Item2, span2.Item1); } if (includeEndPoints) { return (( (span1.Item1 <= span2.Item1 && span1.Item2 >= span2.Item1) || (span1.Item1 <= span2.Item2 && span1.Item2 >= span2.Item2) ) || ( (span2.Item1 <= span1.Item1 && span2.Item2 >= span1.Item1) || (span2.Item1 <= span1.Item2 && span2.Item2 >= span1.Item2) )); } else { return (( (span1.Item1 < span2.Item1 && span1.Item2 > span2.Item1) || (span1.Item1 < span2.Item2 && span1.Item2 > span2.Item2) ) || ( (span2.Item1 < span1.Item1 && span2.Item2 > span1.Item1) || (span2.Item1 < span1.Item2 && span2.Item2 > span1.Item2) ) || ( span1.Item1 == span2.Item1 && span1.Item2 == span2.Item2 )); } } } } 

testing：

 static void Main(string[] args) { Random r = new Random(); DateTime d1; DateTime d2; DateTime d3; DateTime d4; for (int i = 0; i < 100; i++) { d1 = new DateTime(2012,1, r.Next(1,31)); d2 = new DateTime(2012,1, r.Next(1,31)); d3 = new DateTime(2012,1, r.Next(1,31)); d4 = new DateTime(2012,1, r.Next(1,31)); Console.WriteLine("span1 = " + d1.ToShortDateString() + " to " + d2.ToShortDateString()); Console.WriteLine("span2 = " + d3.ToShortDateString() + " to " + d4.ToShortDateString()); Console.Write("\t"); Console.WriteLine(HelperFunctions.AreSpansOverlapping( new Tuple<DateTime, DateTime>(d1, d2), new Tuple<DateTime, DateTime>(d3, d4), true //or use False, to ignore span's endpoints ).ToString()); Console.WriteLine(); } Console.WriteLine("COMPLETE"); System.Console.ReadKey(); }