The pattern: minimise the maximum
The smallest capacity, speed or time that still gets the job done: guess a value, check it with one greedy pass, and search for the smallest that passes.
What the pattern is
The question asks for the smallest value of some limit (a capacity, a rate, a deadline, the largest part of a split) under which a task can still be completed. Constructing the best arrangement directly is hard. Checking whether a given limit is enough is easy, usually one greedy pass. And a larger limit is never worse than a smaller one. That is a first-true search over limits, with the greedy pass as the test.
Minimise the maximum
solve(input)
- lo = the smallest limit that could possibly work; hi = one that certainly does.
- feasible(c): simulate the task under limit c greedily; return whether it finishes within the budget.
- First-true search: while lo < hi, mid = lo + (hi − lo) / 2; if feasible(mid), hi = mid, else lo = mid + 1.
- Return lo.
How to recognise it
- "The minimum capacity / speed / time / largest sum such that …", with a budget: within D days, in h hours, into k parts, by the deadline.
- The answer is a number from a range you can bound, not a choice among the elements.
- You can say why it is monotone: anything that can be done with limit c can be done with limit c + 1.
- Constraints like n up to 10⁵ and values up to 10⁹: the intended cost is O(n log(range)).
Why the greedy check is right
In the shipping problem the check loads each day with packages until the next one would overflow, then starts a new day. No other loading uses fewer days: whatever an optimal loading puts on day one, the greedy loading puts at least as many packages there, and the same argument repeats day by day. This "stay ahead" argument is the proof to give for most checks in this module. Say it in one sentence; the interviewer wants to hear that you know a check needs one.
Worked example
The smallest ship capacity for six packages in three days.
Each test runs the greedy split for one capacity.
-
Step 1 / 7lo7hi27
Packages 4, 7, 2, 6, 5, 3 in order, 3 days. No capacity below the heaviest package, 7, can work, and the total, 27, ships everything in one day.
-
Step 2 / 7lo7mid17hi27
Capacity 17: [4, 7, 2] [6, 5, 3], 2 days. 17 works, so the answer is 17 or smaller: hi = 17.
-
Step 3 / 7lo7mid12hi17
Capacity 12: [4, 7] [2, 6] [5, 3], 3 days. 12 works, so the answer is 12 or smaller: hi = 12.
-
Step 4 / 7lo7mid9hi12
Capacity 9: [4] [7, 2] [6] [5, 3], 4 days. 9 fails, so does everything below it: lo = 10.
-
Step 5 / 7lo10mid11hi12
Capacity 11: [4, 7] [2, 6] [5, 3], 3 days. 11 works, so the answer is 11 or smaller: hi = 11.
-
Step 6 / 7lo10mid10hi11
Capacity 10: [4] [7, 2] [6] [5, 3], 4 days. 10 fails, so does everything below it: lo = 11.
-
Step 7 / 7answer11
The smallest capacity is 11: [4, 7] [2, 6] [5, 3]. Capacity 10 needs 4 days.
One O(n) pass per test, and about log₂ of the range of capacities tests.
The problems, side by side
Every problem in this module is the same loop. What changes is the range and the check.
| Problem | Range | feasible(x) |
|---|---|---|
| Smallest ship capacity | max weight to total weight | greedy split uses at most D days |
| Split to minimise the largest part | max element to total | greedy split uses at most k parts |
| Slowest rate that clears every queue | 1 to the largest queue | Σ ⌈pile / x⌉ ≤ h |
| First day enough flowers are open | earliest to latest bloom day | runs of open flowers give at least m bouquets of k; −1 if m × k > n |
| Earliest time a fleet completes its trips | 1 to min(time) × totalTrips | Σ ⌊x / time[i]⌋ ≥ totalTrips |
| Least time to repair every car | 1 to min(rank) × cars² | Σ ⌊√(x / rank)⌋ ≥ cars |
Two of these overflow 32-bit integers easily: min(time) × totalTrips, and rank × cars². Use 64-bit arithmetic for the bounds and inside the check, and compute ⌊√(x / rank)⌋ with an integer square root rather than a floating-point one near large values.