Effizient überlappende Zeitbereiche in Python finden ⇐ Python

[Anonymous]

Ich habe eine Liste von Zeitbereichen, die als Tupel von DateTime -Objekten dargestellt werden: < /p>
time_ranges = [
(datetime(2023, 10, 26, 10, 0, 0), datetime(2023, 10, 26, 11, 0, 0)),
(datetime(2023, 10, 26, 10, 30, 0), datetime(2023, 10, 26, 12, 0, 0)),
(datetime(2023, 10, 26, 13, 0, 0), datetime(2023, 10, 26, 14, 0, 0)),
(datetime(2023, 10, 26, 13, 30, 0), datetime(2023, 10, 26, 15, 0, 0)),
(datetime(2023, 10, 26, 15, 30, 0), datetime(2023, 10, 26, 16, 0, 0)),
]
< /code>
Ich muss alle überlappenden Zeitbereiche in dieser Liste effizient finden. Zwei Zeitbereiche überschneiden sich, wenn sie eine gemeinsame Zeit haben. Die Ausgabe sollte eine Liste von Tupeln sein, wobei jedes Tupel die Indizes der überlappenden Bereiche enthält. Für das obige Beispiel wäre die gewünschte Ausgabe: < /p>
overlapping_ranges = [
(0, 1),
(2, 3),
]
< /code>
Ich habe einen naiven Ansatz mit verschachtelten Schleifen ausprobiert, um jeden Bereich mit jedem anderen Bereich zu vergleichen, aber dies hat o (n^2) Komplexität und ist für meinen großen Datensatz zu langsam. 13:00)).