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

Das ist meine Lösung:

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

Ich habe es mit 100 % Abdeckung getestet.

Answer 2

Wie wäre es mit einer individuellen Intervall-Baum Struktur? Sie müssen sie ein wenig anpassen, um zu definieren, was es bedeutet, wenn sich zwei Intervalle in Ihrem Bereich "überschneiden".

Diese Frage könnte Ihnen dabei helfen, eine Standardimplementierung eines Intervallbaums in C# zu finden.

Answer 3

Prüfen Sie diese einfache Methode (es wird empfohlen, diese Methode in Ihre dateUtility

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

Answer 4

Ich glaube nicht, dass der Rahmen selbst diese Klasse hat. Vielleicht eine Drittanbieter-Bibliothek...

Aber warum nicht eine Klasse Period value-object erstellen, um diese Komplexität zu bewältigen? Auf diese Weise können Sie sicherstellen, andere Einschränkungen, wie die Validierung Start vs Ende Datumsangaben. Etwas wie:

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

Auf diese Weise können Sie jeden Zeitraum einzeln vergleichen...

Answer 5

Versuchen Sie dies. Mit dieser Methode wird festgestellt, ob sich (zwei) Datumsbereiche überschneiden, unabhängig von der Reihenfolge der Eingabeargumente der Methode. Sie kann auch mit mehr als zwei Datumsbereichen verwendet werden, indem jede Kombination von Datumsbereichen einzeln überprüft wird (z.B. bei 3 Datumsbereichen, führen Sie span1 gegen span2 , span2 gegen span3 y span1 gegen 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
                ));
            }
        }
    }
}

Test:

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