Wielokrotne porównanie zakresów dat dla nakładania się: jak to zrobić wydajnie?

Question

Aby sprawdzić czy pokrywają się w dwóch różnych dateranges, {Start1, End1} i {Start2, End2} ja sprawdzających:

if ((Start1 <= End2) && (End1 >= Start2)) 
{ 
    //overlap exists 
} 

Pytanie, co jest dobrym sposobem, aby porównać nakładania gdybym miał powiedzmy pięć dateranges? .

sprawdzenie, czy któreś z nich się nie nakładają?

Jeśli mam wiele zakresów dat, jak ustalić, czy któryś z tych zakresów pokrywa się?

Answer 1

znaleźć, jeśli wszystkie są nakładających

static bool Overlap(params Tuple<DateTime, DateTime>[] ranges) 
{ 
    for (int i = 0; i < ranges.Length; i++) 
    { 
     for (int j = i + 1; j < ranges.Length; j++) 
     { 
      if (!(ranges[i].Item1 <= ranges[j].Item2 && ranges[i].Item2 >= ranges[j].Item1)) 
       return false; 

     } 
    } 
    return true; 
} 

znaleźć jeśli zachodzą

static bool Overlap(params Tuple<DateTime, DateTime>[] ranges) 
{ 
    for (int i = 0; i < ranges.Length; i++) 
    { 
     for (int j = i + 1; j < ranges.Length; j++) 
     { 
      if (ranges[i].Item1 <= ranges[j].Item2 && ranges[i].Item2 >= ranges[j].Item1) 
       return true; 

     } 
    } 
    return false; 
} 

Answer 2

Jeśli dobrze rozumiem, chcesz odpowiedzieć na pytanie: Czy dwa z tych zakresów pokrywają się? Posortuj je zgodnie z ich końcem po lewej stronie, a następnie przeprowadź wyszukiwanie, aby sprawdzić, czy 1 pokrywa się 2, czy 2 pokrywa 3 itd. Jeśli istnieje nakładanie się, zostanie to znalezione. Nie wierzę, że jest jakikolwiek sposób, aby odpowiedzieć na twoje pytanie, aby uzyskać dowolną listę interwałów, nie biorąc co najmniej O (n log n) czasu, a to, co je sortuje będzie cię kosztować.

Alternatywnie, być może chcesz odpowiedzieć na pytanie: Czy są jakieś dwa z tych zakresów, które nie pokrywają się z? (Na pierwszy rzut oka jest to pytanie zadane przez ciebie, ale (1) wydaje się to dziwne i (2) powyższy komentarz wydaje się wskazywać, że nie o to ci chodzi.) Aby to sprawdzić, znajdź interwał z lewym skrajnym prawym końcem i interwałem z prawostronnym lewym końcem i zobacz, czy zachodzą na siebie. (Jeśli któryś z twoich dwóch przedziałów nie zachodzą na siebie, te dwa nie.)

Answer 3

DateTime h1 = historyRecord.serviceStartDate; 
    DateTime h2 = historyRecord.serviceEndDate; 
    DateTime r1 = record.serviceStartDate; 
    DateTime r2 = record.serviceEndDate; 
    if (!((h1 > r1 && h1 > r2 && h2 > r1 && h2 > r2) || 
     (h1 < r1 && h1 < r2 && h2 < r1 && h2 < r2))) 
     { 
     count += 1; 
     } 

Answer 4

Spróbuj tego:

private bool intersects(DateTime r1start, DateTime r1end, 
          DateTime r2start, DateTime r2end) 
    { 
     return (r1start == r2start) 
      || (r1start > r2start ? 
       r1start <= r2end : r2start <= r1end); 
    } 

Answer 5

Sprawdź to Algorithm to detect overlapping periods w skrócie:

Proste sprawdzenie, czy nakładają się dwa okresy.

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

Lub w kodzie ...

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