Efficiently Finding Overlapping Time Ranges in Python

Efficiently Finding Overlapping Time Ranges in Python
python
Ethan Jackson

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

Related Articles