Merge each user's overlapping subscription intervals and total the covered days
spans is a list of (user_id, start, end) subscription intervals, where start and end are day numbers and a span covers [start, end] inclusive. A user's spans may overlap and may arrive out of order. Return a dict mapping each user to the total number of distinct days they were subscribed — a day covered by two spans counts once.
def covered_days(spans: list[tuple[str, int, int]]) -> dict[str, int]:
# your code hereWrite the implementation.
Bucket the spans by user, then per user sort by start and sweep once: hold a current interval, extend its end when the next start overlaps, else close it (adding end - start + 1 days) and open a new one. Summing closed lengths counts each day once.
- ✗Summing span lengths, double-counting overlapping days
- ✗Merging intervals across users instead of within each user
- ✗Sweeping without sorting each user's intervals first
- →How would half-open intervals
[start, end)change the arithmetic? - →What is the time complexity per user?
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.
