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
Java 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
int coverageGap(List<Shift> shifts, int lengthMinutes) {
}Worked examples
| Call | Result |
|---|---|
coverageGap(Main.<Shift>ls(new Shift(300, 600), new Shift(900, 1200)), 1440) | 300 |
coverageGap(Main.<Shift>ls(new Shift(0, 120), new Shift(60, 180)), 480) | 300 |
coverageGap(Main.<Shift>ls(new Shift(0, 100), new Shift(500, 600)), 1200) | 600 |
coverageGap(Main.<Shift>ls(new Shift(0, 1440)), 1440) | 0 |
Hint
Sort by start, merge the spans while tracking the largest hole between them.
Reference solution in Java
int coverageGap(List<Shift> shifts, int lengthMinutes) {
if (shifts.isEmpty()) return lengthMinutes;
List<Shift> sorted = new ArrayList<>(shifts);
sorted.sort((a, b) -> Integer.compare(a.start, b.start));
int best = sorted.get(0).start;
int curEnd = sorted.get(0).end;
for (int i = 1; i < sorted.size(); i++) {
Shift s = sorted.get(i);
if (s.start > curEnd) best = Math.max(best, s.start - curEnd);
curEnd = Math.max(curEnd, s.end);
}
return Math.max(best, lengthMinutes - curEnd);
}