Command Palette

Search for a command to run...

Hectal
Problem 11.8 · Binary SearchMedium

Capacity to Ship Packages Within D Days

PatternBinary Search on the AnswerGreedy Choice

What it teaches: A greedy feasibility check (fill each day until the next package won't fit) plus binary search on capacity.

Practise it on judges as “Capacity To Ship Packages Within D Days”.

The problem

Packages with weights must ship in order over days days. Each day you load packages in order up to the ship's capacity. Return the least capacity that ships everything within days.

Example 1

Input: weights = [1,2,3,4,5,6,7,8,9,10], days = 5
Output: 15

Example 2

Input: weights = [3,2,2,4,1,4], days = 3
Output: 6

Constraints

  • 1 ≤ days ≤ weights.length ≤ 5 × 10⁴
  • 1 ≤ weight ≤ 500

Pattern clues in the wording

  • → "Least capacity" such that it fits in D days
  • → Bigger capacity never needs more days

These clues point to Binary Search on the Answer: When you can check "is answer x good enough?" and the check is monotonic, binary search over possible answers.

Stuck? Take one hint at a time

Solution.java · starter
class Solution {
    public int shipWithinDays(int[] weights, int days) {
        return 0;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#InputExpected
1
weights = [1,2,3,4,5,6,7,8,9,10]
days = 5
15
2
weights = [3,2,2,4,1,4]
days = 3
6
3
weights = [1,2,3,1,1]
days = 4
3

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Optimal: binary search capacity · O(n log(total))
1

Optimal: binary search capacity

Time O(n log(total)) Space O(1)

lo = max weight, hi = total weight. feasible(c): walk the packages, starting a new day whenever the next one would exceed c; feasible if days used ≤ D.

Approach 1
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 used = 1, load = 0;
            for (int w : weights) {
                if (load + w > mid) { used++; load = 0; }
                load += w;
            }
            if (used <= days) hi = mid;
            else lo = mid + 1;
        }
        return lo;
    }
}

Verdict: Greedy check + binary search.

Before you submit

Edge cases and common mistakes

Test these inputs

  • days = 1 (capacity = total)
  • days = n (capacity = max weight)

Mistakes people make

  • Starting lo at 1: capacities below the heaviest package can never work (the greedy loop would undercount days).

Interview

Follow-up questions

Why is the greedy check correct?