Efficiently Finding Overlapping Time Ranges in Python

I have a list of time ranges represented as tuples of datetime objects:

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)),
]

I need to efficiently find all overlapping time ranges within this list. Two time ranges overlap if they share any common time. The output should be a list of tuples, where each tuple contains the indices of the overlapping ranges. For the example above, the desired output would be:

overlapping_ranges = [
    (0, 1),
    (2, 3),
]

I've tried a naive approach using nested loops to compare each range with every other range, but this has O(n^2) complexity and is too slow for my large dataset.

It would be helpful if the solution could also handle cases where a time range completely encompasses another time range (e.g., (10:00, 14:00) overlaps with (11:00, 13:00)).

Answer

I think using sweep line algorithm will the best solution.

The full code is provided below:

from datetime import datetime
from typing import List, Tuple

def find_overlapping_ranges(
    time_ranges: List[Tuple[datetime, datetime]]
) -> List[Tuple[int, int]]:
    events = []
    for idx, (start, end) in enumerate(time_ranges):
        events.append((start, 'start', idx))
        events.append((end, 'end', idx))
    events.sort(key=lambda x: (x[0], x[1] == 'end'))
    active = set()
    overlaps = []
    for time, event_type, idx in events:
        if event_type == 'start':
            for active_idx in active:
                overlaps.append((active_idx, idx))
            active.add(idx)
        else:
            active.remove(idx)
    return overlaps

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)),
]
overlapping_ranges = find_overlapping_ranges(time_ranges)
print(overlapping_ranges)

Output:

[(0, 1), (2, 3)]