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).
CoverageGap(shifts: list<Shift>, lengthMinutes: int) → int
C# needs a compiler and Drill does not host one yet, so this page is the reference rather than an exercise: the problem, worked examples, and the solution in full. To type it out, the same problem runs in Python.
Where you start
public int CoverageGap(List<Shift> shifts, int lengthMinutes) {
}Worked examples
| Call | Result |
|---|---|
CoverageGap(new List<Shift> { new Shift(300, 600), new Shift(900, 1200) }, 1440) | 300 |
CoverageGap(new List<Shift> { new Shift(0, 120), new Shift(60, 180) }, 480) | 300 |
CoverageGap(new List<Shift> { new Shift(0, 100), new Shift(500, 600) }, 1200) | 600 |
CoverageGap(new List<Shift> { new Shift(0, 1440) }, 1440) | 0 |
Hint
Sort by start, merge the spans while tracking the largest hole between them.
Reference solution in C#
public int CoverageGap(List<Shift> shifts, int lengthMinutes) {
if (shifts.Count == 0) return lengthMinutes;
var sorted = shifts.OrderBy(s => s.Start).ToList();
int best = sorted[0].Start;
int curEnd = sorted[0].End;
foreach (var s in sorted.Skip(1)) {
if (s.Start > curEnd) best = Math.Max(best, s.Start - curEnd);
curEnd = Math.Max(curEnd, s.End);
}
return Math.Max(best, lengthMinutes - curEnd);
}