检测重叠周期的算法

Question

我要检测两个时间段是否重叠.
每个期间都有开始日期和结束日期.
我需要检测我的第一个时间段(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

(案例4在案例1或案例2中被记入帐户)

它有效,但似乎效率不高.

所以,首先在c#中有一个现有的类可以对此进行建模(一个时间段),类似于时间跨度,但具有固定的开始日期.

其次:是否已经有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

您可以创建可重用的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

我正在建立一个预订系统并找到了这个页面.我只对范围交叉感兴趣,所以我构建了这个结构; 使用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,
}

Answer 5

这是我的解决方案：

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%。

Answer 6

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

---------|---|
---|---|                > 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不重叠