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
int coverageGap(std::vector<Shift> shifts, int lengthMinutes) {
}Worked examples
| Call | Result |
|---|---|
coverageGap(std::vector<Shift>{Shift{300, 600}, Shift{900, 1200}}, 1440) | 300 |
coverageGap(std::vector<Shift>{Shift{0, 120}, Shift{60, 180}}, 480) | 300 |
coverageGap(std::vector<Shift>{Shift{0, 100}, Shift{500, 600}}, 1200) | 600 |
coverageGap(std::vector<Shift>{Shift{0, 1440}}, 1440) | 0 |
Hint
Sort by start, merge the spans while tracking the largest hole between them.
Reference solution in C++
int coverageGap(std::vector<Shift> shifts, int lengthMinutes) {
if (shifts.empty()) return lengthMinutes;
std::vector<Shift> sorted = shifts;
std::sort(sorted.begin(), sorted.end(), [](const Shift& a, const Shift& b) { return a.start < b.start; });
int best = sorted[0].start;
int curEnd = sorted[0].end;
for (size_t i = 1; i < sorted.size(); i++) {
const auto& s = sorted[i];
if (s.start > curEnd) best = std::max(best, s.start - curEnd);
curEnd = std::max(curEnd, s.end);
}
return std::max(best, lengthMinutes - curEnd);
}