Algorithmus zur Erkennung sich überschneidender Zeiträume

Question

Ich muss erkennen, ob sich zwei Zeiträume überschneiden.
Jeder Zeitraum hat ein Anfangs- und ein Enddatum.
Ich muss feststellen, ob sich mein erster Zeitraum (A) mit einem anderen Zeitraum (B/C) überschneidet.
In meinem Fall, wenn der Anfang von B gleich dem Ende von A ist, überschneiden sie sich nicht (auch umgekehrt)
Ich habe die folgenden Fälle gefunden:

Also mache ich das eigentlich so:

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

(Der Fall 4 wird entweder in Fall 1 oder in Fall 2 berücksichtigt)

Es Werke aber es scheint nicht sehr effizient zu sein.

Also, zunächst gibt es eine vorhandene Klasse in c#, die dies (ein Zeitraum), so etwas wie eine Zeitspanne, aber mit einem festen Startdatum modellieren kann.

Zweitens: Gibt es bereits einen c#-Code (wie in der DateTime Klasse), die dies bewältigen kann?

Drittens: Wenn nein, wie würden Sie vorgehen, um diesen Vergleich so schnell wie möglich durchzuführen?

Answer 1

Einfache Prüfung, ob sich zwei Zeiträume überschneiden:

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

oder in Ihrem Code:

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

(Verwendung <= 代わりに < falls Sie es sich anders überlegen, ob Sie sagen wollen, dass sich zwei Zeiträume, die sich gerade berühren, überschneiden).

Answer 2

Es gibt eine wunderbare Bibliothek mit guten Bewertungen auf CodeProject: http://www.codeproject.com/Articles/168662/Time-Period-Library-for-NET

Diese Bibliothek leistet eine Menge Arbeit in Bezug auf Überlappung, Überschneidung usw. Es ist zu groß, um alles zu kopieren/einzufügen, aber ich werde sehen, welche spezifischen Teile für Sie nützlich sein können.

Answer 3

Sie können eine wiederverwendbare Range-Musterklasse erstellen:

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

Sie können alle Methoden hinzufügen, die Sie benötigen, um Bereiche zusammenzuführen, Schnittpunkte zu ermitteln usw...

Answer 4

Ich baue gerade ein Buchungssystem auf und habe diese Seite gefunden. Ich interessiere mich nur für Bereichsüberschneidungen, also habe ich diese Struktur gebaut; es ist genug, um mit DateTime-Bereichen zu spielen.

Sie können die Schnittmenge prüfen und feststellen, ob ein bestimmtes Datum im Bereich liegt, und die Schnittpunkttyp und das Wichtigste: Sie können den geschnittenen Bereich abrufen.

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

Dieser Code prüft, ob sich zwei Intervalle überschneiden.

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

Algorithmus:

x1 < y2
and
x2 > y1

Beispiel 12:00 - 12:30 überschneidet sich nicht mit 12:30 13:00