Problems › Python › scheduling
Largest uncovered stretch of the day
A support desk publishes shifts and wants the longest run of minutes during the working day where nobody is on. The day has lengthMinutes total.
- Shifts are given unsorted.
- Before the first shift and after the last also count as uncovered.
- Coverage from a shift is [start, end).
coverage_gap(shifts: list<Shift>, length_minutes: int) → int
Where you start
def coverage_gap(shifts: list[Shift], length_minutes: int) -> int:
Worked examples
| Call | Result |
|---|---|
coverage_gap([Shift(start=300, end=600), Shift(start=900, end=1200)], 1440) | 300 |
coverage_gap([Shift(start=0, end=120), Shift(start=60, end=180)], 480) | 300 |
coverage_gap([Shift(start=0, end=100), Shift(start=500, end=600)], 1200) | 600 |
coverage_gap([Shift(start=0, end=1440)], 1440) | 0 |
Hint
Sort by start, merge the spans while tracking the largest hole between them.
Reference solution in Python
def coverage_gap(shifts: list[Shift], length_minutes: int) -> int:
if not shifts:
return length_minutes
sorted_s = sorted(shifts, key=lambda s: s.start)
best = sorted_s[0].start
cur_end = sorted_s[0].end
for s in sorted_s[1:]:
if s.start > cur_end:
best = max(best, s.start - cur_end)
cur_end = max(cur_end, s.end)
return max(best, length_minutes - cur_end)