Packages with weights weights[i] sit on a conveyor belt and must be shipped in the given order within days days. Each day the ship is loaded with consecutive packages from the front of the belt, as long as their total does not exceed the ship's capacity. Return the smallest capacity that ships everything within days days.
- 1 <= days <= weights.length <= 5 * 10^4
- 1 <= weights[i] <= 500
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
Trying every capacity from max(weights) up to sum(weights) and simulating each is O(n * sum), too slow. The feasibility check is monotonic: a bigger ship never needs more days. So we binary search on the capacity. For a candidate capacity, a greedy pass (keep loading until the next package does not fit, then start a new day) gives the minimum number of days for that capacity in O(n).
Algorithm
- Set
lo = max(weights)andhi = sum(weights). - While
lo < hi, takemidand count the days needed with capacitymidusing the greedy pass. - If the days needed are at most
days,midworks:hi = mid. - Otherwise the ship is too small:
lo = mid + 1. - Return
lo.
O(n log S), where S = sum(weights)Space: O(1)lo at 1 instead of max(weights) is a classic bug: the greedy check then has to handle a package that never fits, and a careless version loops forever or undercounts days.class Solution: def shipWithinDays(self, weights: List[int], days: int) -> int: def days_needed(cap): d, load = 1, 0 for w in weights: if load + w > cap: # does not fit: start a new day d += 1 load = 0 load += w return dΒ lo, hi = max(weights), sum(weights) while lo < hi: mid = (lo + hi) // 2 if days_needed(mid) <= days: hi = mid # works, try smaller else: lo = mid + 1 # too small return lo