Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. The capacity must be at least the heaviest package and at most the total weight.
  2. 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