Finden Sie heraus, ob sich die Datumsangaben in einer Liste von N Paaren überschneiden

Question

Angesichts der Liste von Startzeiten und Beginnzeiten möchte ich herausfinden, ob die Liste überlappende Einträge enthält:

timesok = [('9:30', '10:00'), ('10:00', '10:30'), ('10:30', '11:00')]

wrongtimes1 = [('9:30', '10:00'), ('9:00', '10:30'), ('10:30', '11:00')]
wrongtimes2=[('9:30', '10:00'), ('10:00', '10:30'), ('9:15', '9:45')]

Ich habe einige Codezeilen aus dieser ähnlichen Frage entlehnt, um überlappende Datenpaare zu testen:

def test_overlap(dt1_st, dt1_end, dt2_st, dt2_end):

    r1 = Range(start=dt1_st, end=dt1_end)
    r2 = Range(start=dt2_st, end=dt2_end)
    latest_start = max(r1.start, r2.start)
    earliest_end = min(r1.end, r2.end)
    overlap = (earliest_end - latest_start)
    return overlap.seconds

Meine Funktion zum Testen der Einträge in der Liste:

def find_overlaps(times):
    pairs = list(combinations(times, 2))
    print pairs
    for pair in pairs:
        start1 = dt.strptime(pair[0][0], '%H:%M')
        end1 = dt.strptime(pair[0][1], '%H:%M')
        start2 = dt.strptime(pair[1][0], '%H:%M')
        end2 = dt.strptime(pair[1][1], '%H:%M')
        yield test_overlap(start1, end1, start2, end2) > 0

Wenn es verwendet wird, funktioniert es wie folgt:

In [257]: list(find_overlaps(timesok))
[(('9:30', '10:00'), ('10:00', '10:30')), (('9:30', '10:00'), ('10:30', '11:00')), (('10:00', '10:30'), ('10:30', '11:00'))]
Out[257]: [False, False, False]

In [258]: list(find_overlaps(wrongtimes1))
[(('9:30', '10:00'), ('9:00', '10:30')), (('9:30', '10:00'), ('10:30', '11:00')), (('9:00', '10:30'), ('10:30', '11:00'))]
Out[258]: [True, False, False]

In [261]: list(find_overlaps(wrongtimes2))
[(('9:30', '10:00'), ('10:00', '10:30')), (('9:30', '10:00'), ('9:15', '9:45')), (('10:00', '10:30'), ('9:15', '9:45'))]
Out[261]: [False, True, False]

Allerdings:

1. Ich bin immer noch unschlüssig, ob dies sehr effizient für große Listen ist.
2. Ich frage mich, ob jemand eine bessere Lösung anbieten kann?

Answer 1

Ich schlage vor, auf diese Weise die Überlappung zu testen, einen Weg, alle Schnittpunkte eines Datums zu finden:

def test_overlap(dt1_st, dt1_end, dt2_st, dt2_end):
    return not (dt1_st < dt2_end and dt1_end >dt2_st)

Das deckt alle Möglichkeiten der Überlappung ab

Answer 2

Dies ähnelt dem Intervalloverlapping-Problem. Erklärung des Beitrags von pkacprzak.

Sortiere eine Liste von Ereignissen nach Zeit. Behalte eine andere Liste von aktiven Elementen bei.

Verarbeite linear wie folgt.

Für jedes Ereignis/Element.

1. Füge der Liste der aktiven Elemente hinzu, wenn der Startpunkt ist.
2. Entferne aus der Liste der aktiven Elemente, wenn der Endpunkt ist.
3. Zusätzlich werden bei jedem Startpunkt die aktuellen aktiven Elemente mit dem aktuellen Element überlappen.

Sieh dir auch andere Lösungen für Intervallüberlappungen an, wie diese. wie man Intervalle effizient überlappt

Answer 3

Wenn keine zwei Paare gleichzeitig beginnen, könnte man die Zeitstempel als numerische Werte in "Minuten seit Mitternacht" behandeln, dann die Eingabelist nach der Startzeit sortieren und überprüfen, ob die Endzeit eines Elements größer ist als die Startzeit des nächsten Elements:

from operator import itemgetter
from itertools import izip

def asNumber(s):
    colon = s.find(':')
    return int(s[:colon]) * 60 + int(s[colon+1:])

def isValid(l):
  numericPairs = [(asNumber(a), asNumber(b)) for (a,b) in l]
  sortedPairs = sorted(numericPairs, key=itemgetter(0))
  return all(startB >= endA for ((startA, endA), (startB, endB)) in izip(sortedPairs, sortedPairs[1:]))