Problems › TypeScript › 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).
coverageGap(shifts: list<Shift>, lengthMinutes: int) → int
Where you start
function coverageGap(shifts: Shift[], lengthMinutes: number): number {
}Worked examples
| Call | Result |
|---|---|
coverageGap([{"start":300,"end":600},{"start":900,"end":1200}], 1440) | 300 |
coverageGap([{"start":0,"end":120},{"start":60,"end":180}], 480) | 300 |
coverageGap([{"start":0,"end":100},{"start":500,"end":600}], 1200) | 600 |
coverageGap([{"start":0,"end":1440}], 1440) | 0 |
Hint
Sort by start, merge the spans while tracking the largest hole between them.
Reference solution in TypeScript
function coverageGap(shifts: Shift[], lengthMinutes: number): number {
if (!shifts.length) return lengthMinutes;
const sorted = shifts.slice().sort((a, b) => a.start - b.start);
let best = sorted[0].start;
let curEnd = sorted[0].end;
for (let i = 1; i < sorted.length; i++) {
const s = sorted[i];
if (s.start > curEnd) best = Math.max(best, s.start - curEnd);
curEnd = Math.max(curEnd, s.end);
}
return Math.max(best, lengthMinutes - curEnd);
}