Поиск перекрывающихся интервалов в наборе интервалов

Закодируйте все границы интервала в виде 1:+P1, 7:-P1. Затем отсортируйте все границы в хронологическом порядке и просканируйте по возрастанию времени. Также обновляйте список лиц, присутствующих при «выполнении» операций вставки или удаления.

{} 1:+P1 {P1} 2:+P2 {P1, P2} 3:+P3 {P1, P2, P3} 4:-P3 {P1, P2} 5:-P2 {P1} ...

Каждая конфигурация возникает между одной временной привязкой и следующей.

Некоторые конфигурации могут со временем повторяться, но вы не указали, как с ними работать. При указанном выше методе они будут перечислены отдельно.

Один подход, предполагающий, что ввод является словарем человека -> интервал:

from collections import defaultdict
from itertools import pairwise

data = {"P1": (1, 7),
        "P2": (2, 5),
        "P3": (3, 4),
        "P4": (6, 8)}

table = defaultdict(list)
for key, (start, end) in data.items():
    for i, j in pairwise(range(start, end + 1)):
        table[(i, j)].append(key)

result = {k: v for k, v in table.items() if len(v) > 1}

for key, value in result.items():
    print(value, key)

Выход

['P1', 'P2'] (2, 3)
['P1', 'P2', 'P3'] (3, 4)
['P1', 'P2'] (4, 5)
['P1', 'P4'] (6, 7)

В значительной степени вдохновлен Минимальным количеством платформ, необходимым для железнодорожной станции, но с сохранением набора присутствующих людей вместо количества присутствующих поездов:

Также реализация алгоритма намекает в ответе Ива Дауста.

Идея состоит в том, чтобы сначала построить хронологический список всех событий, где событием является либо приход, либо уход человека.

Затем мы повторяем список событий, сохраняя набор присутствующих людей, добавляя прибывающих и удаляя уходящих.

Ниже хронологический список событий реализован как время сопоставления Python dict с событиями Python list, так что события, происходящие в одно и то же время, если таковые имеются, естественным образом группируются вместе.

from operator import itemgetter

data = {
    'P1': [1,7],
    'P2': [2,5],
    'P3': [3,4],
    'P4': [6,8]
}

def get_overlaps(data):
    events = {}
    for person, (start, end) in data.items():
        events.setdefault(start, []).append((person, set.add))
        events.setdefault(end, []).append((person, set.remove))
    # events = {1: [('P1', add)], 2: [('P2', add)], 3: [('P3', add)], 4: [('P3', remove)], 5: [('P2', remove)], 6: [('P4', add)], 7: [('P1', remove)], 8: [('P4', remove)]}
    present_persons = set()
    start_time = 0
    for new_time, grouped_events in sorted(events.items(), key=itemgetter(0)):
        if len(present_persons) >= 2:
            yield (frozenset(present_persons), (start_time, new_time))
        start_time = new_time
        for new_person, add_or_remove in grouped_events:
            add_or_remove(present_persons, new_person)

data = {
    'P1': [1,7],
    'P2': [2,5],
    'P3': [3,4],
    'P4': [6,8]
}
overlaps = list(get_overlaps(data))

print(overlaps)
# [(frozenset({'P2', 'P1'}),       (2, 3)),
#  (frozenset({'P2', 'P1', 'P3'}), (3, 4)),
#  (frozenset({'P2', 'P1'}),       (4, 5)),
#  (frozenset({'P4', 'P1'}),       (6, 7))]

data2 = { # three events at time 5: (P1,remove), (P2,remove), (P4,add) 
    'P1': [1,5],
    'P2': [2,5],
    'P3': [3,4],
    'P4': [5,8]
}

overlaps = list(get_overlaps(data2))

print(overlaps)
# [(frozenset({'P2', 'P1'}), (2, 3)),
#  (frozenset({'P2', 'P1', 'P3'}), (3, 4)),
#  (frozenset({'P2', 'P1'}), (4, 5))]

Этот алгоритм имеет временную сложность O(N), где N — количество человек. Для сравнения, алгоритм в ответе Дани Месехо имеет временную сложность O (TN), где N — количество людей, а T — максимальное время присутствия любого человека, измеряемое количеством мгновений.