mediumCodingMidSeniorStaff
Given package weights in a fixed order, find the smallest ship capacity that delivers them all within D days
5 min readUpdated 2026-08-15
Answer
Short answer
When you cannot construct the answer but can cheaply test a candidate, and that test is monotone, binary search the answer's numeric range instead of the input. The feasibility check here is greedy day-packing, giving O(n log S) time, and the whole implementation hinges on one loop invariant.
Was this answer helpful?
Likely follow-ups
- Change the problem so packages may be reordered. Does the same approach survive?
- How does this change when the answer is a real number rather than an integer?
- Your feasibility check is itself greedy. Prove it computes the minimum number of days.
- When is a library binary search the wrong tool even though the data is sorted?
Related questions
- You are given a sorted array that has been rotated by an unknown amount. Find a target value in logarithmic time.mediumAlso on binary-search and invariants5 min
- Envelopes nest only when both width and height are strictly larger. How many can you nest, and why must equal widths be sorted by height descending?hardAlso on binary-search4 min
- You may use an AI coding assistant in the machine-coding round. What do you still write yourself, and what do you ask it for?mediumAlso on invariants5 min
- A bundle can contain products or other bundles, and the pricing code should not care which it is holding. How would you model that?mediumAlso on invariants6 min