检测重叠周期的算法

我必须检测两个时间段是否重叠 每个周期有一个开始日期和一个结束日期 我需要检测我的第一个时间段(A)是否与另一个时间段(B/C)重叠。< br / > 在我的例子中，如果B的开始等于A的结束，它们不重叠(逆也)
我发现以下情况:

enter image description here

实际上我是这样做的:

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

(情况4在情况1或情况2的账户中被计入)

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

首先，c#中有一个现有的类可以对这个(时间段)进行建模，类似于一个时间跨度，但是有一个固定的开始日期。

其次:是否已经有c#代码(如在DateTime类)可以处理这个问题?

第三:如果没有，你会用什么方法最快地进行比较?

205157 次浏览
小开
最佳答案

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

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

或者在你的代码中:

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

(如果你改变了主意，想说两个交叠的周期，可以用<=代替<。)

小开

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

这个库做了很多关于重叠、交叉等方面的工作。它太大了，不能全部复制/粘贴，但我会看看哪些具体的部分对你有用。

小开

自定义interval-tree结构如何?您必须稍微调整一下，以定义在定义域中两个间隔“重叠”的含义。

这个问题可能会帮助您在c#中找到一个现成的间隔树实现。

小开

你可以创建一个可重用的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; } }
}

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

小开

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

但是为什么不创建一个Period值对象类来处理这种复杂性呢?这样可以确保其他约束，比如验证开始日期时间和结束日期时间。喜欢的东西:

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) { }
}
}

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

小开

我正在建立一个预订系统，发现了这个页面。我只对范围交感兴趣，所以我建了这个结构;使用DateTime范围就足够了。

您可以检查交集并检查特定日期是否在范围内，并获得 交点类型和最重要的:你可以得到交点范围。

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,
}
小开 
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是dateTime类型

小开

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

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

算法:

x1 < y2
and
x2 > y1

例如12:00 - 12:30和12:30 13:00不重叠

小开 
--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

分布逻辑

小开

试试这个。此方法将确定(两个)日期跨度是否重叠，而不考虑方法输入参数的顺序。这也可以用于两个以上的日期跨度，通过单独检查每个日期跨度组合(例如，对于3个日期跨度，运行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
));
}
}
}
}

测试:

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();
}
小开

这是我的解决方案:

public static bool OverlappingPeriods(DateTime aStart, DateTime aEnd,
DateTime bStart, DateTime bEnd)
{
if (aStart > aEnd)
throw new ArgumentException("A start can not be after its end.");


if(bStart > bEnd)
throw new ArgumentException("B start can not be after its end.");


return !((aEnd < bStart && aStart < bStart) ||
(bEnd < aStart && bStart < aStart));
}

我进行了单元测试，覆盖率为100%。

小开

检查这个简单的方法(建议将此方法放在dateUtility中

public static bool isOverlapDates(DateTime dtStartA, DateTime dtEndA, DateTime dtStartB, DateTime dtEndB)
{
return dtStartA < dtEndB && dtStartB < dtEndA;
}

提交答案