Practice › Binary Search
Capacity to Ship Packages
Medium · Binary Search · Asked at Amazon, Google, Flipkart, Microsoft
Packages must be shipped in the given order within d days. Each day the ship carries a contiguous group of packages whose total weight does not exceed its capacity. Print the minimum capacity that ships everything within d days.
Input
First line: n d. Second line: the n weights.
Output
The minimum capacity.
Constraints
- 1 ≤ d ≤ n ≤ 5 · 10^4
- 1 ≤ w[i] ≤ 500
Binary search the answer between max(w) and sum(w). For a capacity, greedily count the days needed.
Example 1
Input
10 5 1 2 3 4 5 6 7 8 9 10
Output
15
Example 2
Input
6 3 3 2 2 4 1 4
Output
6
Hints
- The capacity must be at least the heaviest package and at most the total weight.
- For a fixed capacity, count days greedily (load packages until the next one does not fit). Larger capacity never needs more days — binary search.
Approach
days(cap) fills the ship in order and starts a new day whenever the next package would overflow. It is non-increasing in cap, so binary search the smallest cap in [max(w), sum(w)] with days(cap) ≤ d.
Complexity: O(n log(sum)) time · O(1) extra space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, d;
cin >> n >> d;
vector<long long> w(n);
for (auto &x : w) cin >> x;
auto days = [&](long long cap) {
int used = 1;
long long cur = 0;
for (long long x : w) {
if (cur + x > cap) used++, cur = 0;
cur += x;
}
return used;
};
long long lo = *max_element(w.begin(), w.end()), hi = accumulate(w.begin(), w.end(), 0LL);
while (lo < hi) {
long long mid = (lo + hi) / 2;
if (days(mid) <= d) hi = mid;
else lo = mid + 1;
}
cout << lo << "\n";
return 0;
}Python solution
import sys
data = list(map(int, sys.stdin.read().split()))
n, d, w = data[0], data[1], data[2:]
def days(cap):
used, cur = 1, 0
for x in w:
if cur + x > cap:
used += 1
cur = 0
cur += x
return used
lo, hi = max(w), sum(w)
while lo < hi:
mid = (lo + hi) // 2
if days(mid) <= d:
hi = mid
else:
lo = mid + 1
print(lo)Java solution
import java.util.*;
public class Main {
static long[] w;
static int days(long cap) {
int used = 1;
long cur = 0;
for (long x : w) {
if (cur + x > cap) { used++; cur = 0; }
cur += x;
}
return used;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), d = sc.nextInt();
w = new long[n];
long lo = 0, hi = 0;
for (int i = 0; i < n; i++) {
w[i] = sc.nextLong();
lo = Math.max(lo, w[i]);
hi += w[i];
}
while (lo < hi) {
long mid = (lo + hi) / 2;
if (days(mid) <= d) hi = mid;
else lo = mid + 1;
}
System.out.println(lo);
}
}Solve Capacity to Ship Packages online · All practice problems