Smallest capacity that fits the jobs into maintenance windows

HardAbout 40 minProblem 3 of 3 in Binary searchDraft

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

  1. smallestCapacity([10, 20, 30, 40, 50], 2)returns 9010 + 20 + 30 + 40 = 100 is too much for one window, so split as 10, 20, 30 | 40, 50.
  2. smallestCapacity([7, 2, 5, 10, 8], 3)returns 147, 2, 5 | 10 | 8 needs 14; nothing smaller fits.
  3. smallestCapacity([5, 5, 5], 3)returns 5One 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.

Your solution

Tab indents. Press Esc, then Tab, to leave the editor. Ctrl+Enter runs the examples.

Esc
↑ ↓ to move↵ to open