Smallest capacity that fits the jobs into maintenance windows
A re-solve is due. Start from a blank template and solve it without the editorial. That is what makes the pattern stick.
The problem
A list of maintenance jobs must run in order. They are split across windows maintenance windows: each window runs a contiguous run of the jobs, and the jobs in one window may take at most capacity minutes in total. A job cannot be split across windows, and a window may be left empty.
Return the smallest whole capacity that fits every job into at most windows windows.
- 1 ≤ jobs.length ≤ 200,000
- 1 ≤ jobs[i] ≤ 10,000
- 1 ≤ windows ≤ jobs.length
Examples
smallestCapacity([10, 20, 30, 40, 50], 2)returns9010 + 20 + 30 + 40 = 100 is too much for one window, so split as 10, 20, 30 | 40, 50.smallestCapacity([7, 2, 5, 10, 8], 3)returns147, 2, 5 | 10 | 8 needs 14; nothing smaller fits.smallestCapacity([5, 5, 5], 3)returns5One job per window.
Hints
Hint 1 of 2
For a given capacity, fill windows greedily: put each job in the current window if it fits, otherwise start the next window. That uses the fewest windows for that capacity.
Hint 2 of 2
More capacity never needs more windows. Search capacity between the largest job and the total of all jobs.
Editorial
Opens once you solve the problem, or after three checked attempts.
Read the editorial and a reference solution
Choosing where to cut the list directly is hard: there are far too many ways to split 200,000 jobs. Turn it around and ask a yes-or-no question about a capacity instead: can the jobs fit into the windows with this much room each?
That question has a quick answer. Fill each window greedily, moving to the next window only when the next job does not fit. Leaving room in a window can never save a window later, so the greedy fill uses the fewest windows for that capacity.
A larger capacity never needs more windows, so the answer flips once, and binary search finds the flip. The range matters: below the largest job nothing fits, however many windows there are, and the greedy check misreads such a capacity. Start at the largest job and end at the total.
Dividing the total by the number of windows is a lower bound, not the answer: in [7, 2, 5, 10, 8] with three windows it gives 11, but no split into contiguous runs fits in 11.
function smallestCapacity(jobs, windows) {
const fits = (cap) => {
let used = 1, load = 0;
for (const j of jobs) {
if (load + j > cap) { used++; load = 0; if (used > windows) return false; }
load += j;
}
return true;
};
let lo = jobs.reduce((a, b) => Math.max(a, b), 0), hi = jobs.reduce((a, b) => a + b, 0);
while (lo < hi) {
const mid = lo + Math.floor((hi - lo) / 2);
if (fits(mid)) hi = mid; else lo = mid + 1;
}
return lo;
}Complexity. O(n log S) for n jobs whose total is S: one greedy pass per guess, about thirty guesses.
Your solution
TypeScript types are removed before the tests run, not checked: the tests judge what the code does.
Tab indents. Press Esc, then Tab, to leave the editor. Ctrl+Enter runs the examples.