Problem Statement
You run an ML training cluster. You have a list of training jobs, where jobs[i] is the GPU memory (in GB) that job i requires. You process jobs in order, and each day you can run a contiguous batch of jobs as long as their total memory doesn't exceed the GPU's capacity.
You must finish ALL jobs within K days. Find the minimum GPU memory capacity (in GB) needed so that all jobs complete within K days.
Constraints
1 <= jobs.length <= 10^51 <= jobs[i] <= 10^61 <= K <= jobs.length- Jobs must be processed in the given order (contiguous batches)
Example
Input: jobs = [7, 2, 5, 10, 8], K = 2
Output: 18
Explanation: With capacity 18: Day 1 runs [7,2,5] (sum 14), Day 2 runs [10,8] (sum 18). Fits in 2 days. No smaller capacity works.
The Insight — Binary Search on the Answer
This looks like a partitioning DP problem, but the elegant solution is binary search on the answer (the capacity itself).
Why it works:
- The answer (capacity) lies between
max(jobs)(must fit the biggest single job) andsum(jobs)(everything in one day). - Capacity has a monotonic property: if capacity
Xlets you finish in ≤ K days, so does any capacity > X. This monotonicity is exactly what binary search needs.
Algorithm:
lo = max(jobs),hi = sum(jobs)- Binary search on capacity. For a candidate capacity
mid, greedily count how many days it takes (start a new day when adding a job would exceedmid). - If days needed ≤ K → try smaller (
hi = mid). Else → need bigger (lo = mid + 1).
The "aha" is recognizing you're binary-searching over the value space of the answer, not over an array. Once you spot the monotonic feasibility check, this pattern unlocks a whole class of "minimize the maximum" problems.
Follow-ups
- Why is the feasibility function (days-needed-for-capacity-X) monotonic?
- What if jobs could be reordered? Does the problem get easier or harder?
- What's the time complexity? (O(n log(sum)))
- How does this relate to "split array into K subarrays minimizing the largest sum"?