Слить перекрывающиеся интервалы подписки каждого пользователя и посчитать покрытые дни
spans — список интервалов подписки (user_id, start, end), где start и end — номера дней, а интервал покрывает [start, end] включительно. Интервалы пользователя могут перекрываться и приходить не по порядку. Верните dict, сопоставляющий каждому пользователю общее число различных дней подписки — день из двух интервалов считается раз.
def covered_days(spans: list[tuple[str, int, int]]) -> dict[str, int]:
# ваш код здесьНапишите реализацию.
Сгруппируйте по пользователю, отсортируйте по началу и пройдите один раз: держите текущий интервал, расширяйте конец при перекрытии, иначе закройте его (прибавив end - start + 1 дней) и откройте новый. Сумма закрытых длин считает каждый день раз.
- ✗Суммировать длины интервалов, дважды считая перекрытия
- ✗Сливать интервалы между пользователями, а не внутри каждого
- ✗Проходить без сортировки интервалов каждого пользователя
- →Как полуоткрытые интервалы
[start, end)изменят арифметику? - →Какова временная сложность на пользователя?
Group spans by user, then treat each user independently: sort by start and merge in a single sweep. The start <= cur_end test detects an overlap with the open interval; otherwise the current interval is closed and its inclusive length end - start + 1 is added.
from collections import defaultdict
def covered_days(spans):
by_user = defaultdict(list)
for user, start, end in spans:
by_user[user].append((start, end))
result = {}
for user, intervals in by_user.items():
intervals.sort()
cur_start, cur_end = intervals[0]
total = 0
for start, end in intervals[1:]:
if start <= cur_end: # overlaps the open interval
cur_end = max(cur_end, end)
else:
total += cur_end - cur_start + 1
cur_start, cur_end = start, end
total += cur_end - cur_start + 1
result[user] = total
return resultFor user a with [(1, 3), (2, 5), (8, 9)] the first two merge into [1, 5] (5 days) and [8, 9] adds 2 — total 7, counting day overlaps once. Sorting is what makes the single sweep correct; without it an out-of-order span breaks the merge.
