Из списка интервалов, поиск всех наборов интервалов, где КАЖДЫЙ интервал в одном наборе перекрывается со всеми интервалами в этом наборе

Вместо того, чтобы запрашивать список интервалов с датой начала и окончания, чтобы получить все интервалы из списка, которые перекрываются только с датой начала и окончания поиска, как лучше всего:

From a list of date intervals, 
Find all unique sets of intervals
Where every interval in each set overlaps with each other interval in that set

В качестве целочисленного примера возьмем список целочисленных интервалов [{1,3},{2,4},{4,5},{5,7},{6,8}]. Из этого списка перечислены все уникальные наборы интервалов, в которых каждый интервал в каждом наборе перекрывается друг с другом:

{ {1,3}, {2,4} }
{ {2,4}, {4,5} }
{ {4,5}, {5,7} }
{ {5,7}, {6,8} }

Вот класс для DateInterval:

from datetime import datetime
class DateInterval(object):
    def __init__(self, start_time, end_time):
        self.start_time = datetime.strptime(start_time, '%Y-%m-%d %H:%M:%S')
        seld.end_time = datetime.strptime(end_time, '%Y-%m-%d %H:%M:%S')

    ''' eq, gt, hash methods removed for clarity '''

Я получу список интервалов, отсортированных по start_time в порядке возрастания:

intervals = [DateInterval(start_time='2015-01-01 08:00:00', end_time='2015-01-01 08:30:00'),
             DateInterval(start_time='2015-01-01 08:00:00', end_time='2015-01-01 10:00:00'),
             DateInterval(start_time='2015-01-01 09:00:00', end_time='2015-01-01 11:00:00'),
             DateInterval(start_time='2015-01-01 10:00:00', end_time='2015-01-01 12:00:00'),
             DateInterval(start_time='2015-01-01 13:00:00', end_time='2015-01-01 16:00:00'),
             DateInterval(start_time='2015-01-01 14:00:00', end_time='2015-01-01 17:00:00'),
             DateInterval(start_time='2015-01-01 15:00:00', end_time='2015-01-01 18:00:00'),
             DateInterval(start_time='2015-01-01 20:00:00', end_time='2015-01-01 22:00:00'),
             DateInterval(start_time='2015-01-01 20:00:00', end_time='2015-01-01 22:00:00')
             ]

(В этом примере списка даты начала и окончания всегда совпадают с часом. Однако вместо этого они могут соответствовать любой секунде (или, возможно, миллисекундам)). После поиска в исчерпывающем списке вопросов по stackoverflow, касающихся перекрывающихся интервалов, Я обнаружил, что дерево интервалов не подходит для интервалов дат).

Мой слегка оптимизированный метод грубой силы состоит из трех задач

1. Определите все неуникальные наборы интервалов, в которых хотя бы один интервал в каждом наборе перекрывается со всеми другими интервалами в этом наборе.
2. Дублируйте результаты шага 1, чтобы найти все уникальные наборы интервалов, где хотя бы один интервал в каждом наборе перекрывается со всеми другими интервалами в этом наборе.
3. Из результатов 1 найдите только те наборы, в которых каждый интервал в одном наборе перекрывается со всеми другими интервалами в этом наборе.

1.

Далее выполняется поиск всех неуникальных наборов, в которых только один интервал в каждом наборе перекрывается с каждым другим интервалом в этом наборе, путем наивного сравнения каждого интервала в списке интервалов со всеми другими интервалами. Предполагается, что список интервалов отсортирован по возрастанию даты и времени, что позволяет break оптимизацию

def search(intervals, start_date, end_date):
    results = []
    for interval in intervals:
        if end_date >= interval.start_time:
            if start_date <= interval.end_time:
                results.append(interval)
        else:
            break # This assumes intervals are sorted by date time ascending

search используется так:

brute_overlaps = []
for interval in intervals:
    brute_overlaps.append(search(intervals, interval.start_time, interval.end_time))

2.

Следующее выполняет дедупликацию списка наборов:

def uniq(l):
    last = object()
    for item in l:
        if item == last:
            continue
        yield item
        last = item

def sort_and_deduplicate(l):
    return list(uniq(sorted(l, reverse=True)))

3.

И следующее находит все наборы, в которых каждый интервал в каждом наборе перекрывается со всеми другими интервалами в этом наборе, путем наивного сравнения каждого интервала в наборе с каждым другим интервалом в этом наборе:

def all_overlap(overlaps):
    results = []
    for overlap in overlaps:
        is_overlap = True
        for interval in overlap:
            for other_interval in [o for o in overlap if o != interval]:
                if not (interval.end_time >= other_interval.start_time and interval.start_time <= other_interval.end_time):
                    is_overlap = False
                    break # If one interval fails
             else:        # break out of
                 continue # both inner for loops
             break        # and try next overlap

        if is_overlap: # all intervals in this overlap set overlap with each other
            results.append(overlap)
    return results