Back to DSA

Capacity To Ship Packages Within D Days

medium
Acceptance: 54%
Binary Search

Packages on a conveyor belt must be loaded onto a ship and delivered in a fixed number of days. Packages must be loaded in their original order, and the ship has a weight capacity that limits how much can be loaded each day. Find the minimum ship capacity that allows all packages to be delivered within the allotted days.

Examples

Example 1:
Input:weights = [3,2,2,4,1,4], days = 3
Output:6
Explanation: Capacity 6: day 1 loads [3,2] (5), day 2 loads [2,4] (6), day 3 loads [1,4] (5).
Example 2:
Input:weights = [5,5,5,5,5], days = 5
Output:5
Explanation: Each package goes on its own day, so minimum capacity is 5.

Hints

Related Problems

Longest Increasing SubsequencemediumSearch in Rotated Sorted ArraymediumFind Peak ElementmediumKoko Eating BananasmediumSplit Array Largest Sumhard
00:00
class Solution {
    public int shipWithinDays(int[] weights, int days) {
        int lo = 0, hi = 0;
        for (int w : weights) { lo = Math.max(lo, w); hi += w; }
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            int d = 1, sum = 0;
            for (int w : weights) {
                if (sum + w > mid) { d++; sum = 0; }
                sum += w;
            }
            if (d <= days) hi = mid;
            else lo = mid + 1;
        }
        return lo;
    }
}
Time complexityO(n * log(sum - max))
Space complexityO(1)