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
Go 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
func coverageGap(shifts []Shift, lengthMinutes int) int {
}Worked examples
| Call | Result |
|---|---|
coverageGap([]Shift{Shift{Start: 300, End: 600}, Shift{Start: 900, End: 1200}}, 1440) | 300 |
coverageGap([]Shift{Shift{Start: 0, End: 120}, Shift{Start: 60, End: 180}}, 480) | 300 |
coverageGap([]Shift{Shift{Start: 0, End: 100}, Shift{Start: 500, End: 600}}, 1200) | 600 |
coverageGap([]Shift{Shift{Start: 0, End: 1440}}, 1440) | 0 |
Hint
Sort by start, merge the spans while tracking the largest hole between them.
Reference solution in Go
func coverageGap(shifts []Shift, lengthMinutes int) int {
if len(shifts) == 0 {
return lengthMinutes
}
sorted := make([]Shift, len(shifts))
copy(sorted, shifts)
sort.Slice(sorted, func(i, j int) bool { return sorted[i].Start < sorted[j].Start })
best := sorted[0].Start
curEnd := sorted[0].End
for _, s := range sorted[1:] {
if s.Start > curEnd && s.Start-curEnd > best {
best = s.Start - curEnd
}
if s.End > curEnd {
curEnd = s.End
}
}
if lengthMinutes-curEnd > best {
return lengthMinutes - curEnd
}
return best
}