2012-11-22 296 views
272

我必須檢測兩個時間段是否重疊。檢測重疊時間的算法

每個時期都有開始日期和結束日期。

我需要檢測我的第一個時間段(A)是否與另一個(B/C)重疊。

在我的情況下,如果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#中有一個現有的類,可以對此進行建模(一段時間),類似於timepsan,但具有固定的開始日期。

其次:是否已經有一個C#代碼(如在Datetime類中)可以處理這個?

第三:如果不是,那麼您將如何使這個比較最快?

+1

期間(C)在案例5中令我困惑。這是否代表不重疊的情況?如果是這樣,你是不是分成兩部分,案例5 B全部在A之前,案例6 A全部在B之前? –

+0

是它不重疊。 – J4N

+3

質量好的問題! – bob

回答

451

簡單的檢查,看看兩個時間段重疊:

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

或代碼:

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

(使用<=而不是<如果你改變主意,想要說的兩個期間,只是互相重疊。)

+1

感謝您的快速響應!優秀!似乎是非常有效的:) – J4N

+3

@ J4N第一次我不得不這樣做,我寫了類似你的代碼,直到有人指出了這一點。只是通過它:) – Rawling

+2

我不明白這是如何涵蓋所有情況。 – doker

3

自定義interval-tree結構如何?您必須稍微調整一下,以定義兩個區間在您的域中「重疊」的含義。

This question可能會幫助您在C#中找到現成的間隔樹實現。

16

您可以創建一個可重用的震盪格局類:

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; } } 
} 

您可以添加需要合併範圍內的所有方法,得到交叉口等等...

+1

好的答案,但是比較應該返回Min.CompareTo(other.Max)<= 0 && other.Min.CompareTo(Max)<= 0; –

+0

'code' public bool InersectsW –

+0

如何使用IoC注入這個類,比如autofac? – Sai

2

我不相信框架本身就有這個類。也許是第三方庫...

但爲什麼不創建一個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) { }  
    } 
} 

這樣,你就能夠單獨比較每個時期......

+0

試試http://www.codeproject.com/Articles/168662/Time-Period-Library-for-NET –

7

我建立一個訂票系統,發現這個頁面。我只對範圍交叉感興趣,所以我建立了這個結構;使用DateTime範圍就足夠了。

您可以檢查交叉口,並檢查特定日期是否在範圍內,並獲取 交叉口類型,最重要的是:您可以獲得相交的Range。

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, 
} 
0
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是日期時間類型

2

此代碼檢查如果兩個區間重疊。

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

算法:

x1 < y2 
and 
x2 > y1 

例如12:00 - 12:30未與12:30 13:00

1
--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 

Distrubution logic

+1

不知道你怎麼能比我接受的那個更好地考慮這個答案? – J4N

0

重疊試試這個。無論方法的輸入參數的順序如何,此方法將確定(兩個)日期跨度是否重疊。這也可以有兩個以上的時間跨度中,通過逐一檢查每個日期跨徑組合爲(前3日期跨度,運行span1span2span2span3span1span3):

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