Getting everything ready for you…

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

0s

Practice › Binary Search

Book Allocation

Hard · Binary Search · Asked at Amazon, Google, Microsoft, Codenation

There are n books with given page counts (in order) and m students. Each student gets a contiguous block of at least one book. Minimise the maximum pages assigned to a student. Print that value, or -1 if m > n.

Input

First line: n m. Second line: n page counts.

Output

The minimum possible maximum, or -1.

Constraints

Binary search on the answer between max(pages) and sum(pages).

Example 1

Input

4 2
12 34 67 90

Output

113

Example 2

Input

3 5
10 20 30

Output

-1

Hints

  1. Guess a limit L on pages per student. Can you split the books so nobody gets more than L?
  2. Greedy check: give books to the current student until the next one would exceed L, then start a new student. Binary search the smallest L that needs ≤ m students.

Approach

If m > n, someone gets no book, so print -1. Otherwise binary search L in [max(pages), sum(pages)]. studentsNeeded(L) fills each student greedily up to L. If at most m students are needed, L works, and so does every larger L. Using fewer than m students is fine because blocks can always be split further while m ≤ n. The smallest working L is the answer.

Complexity: O(n log(sum)) time · O(1) extra space

Solution

C++ solution

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<long long> p(n);
    for (auto &x : p) cin >> x;
    if (m > n) {
        cout << -1 << "\n";
        return 0;
    }
    long long lo = *max_element(p.begin(), p.end()), hi = accumulate(p.begin(), p.end(), 0LL);
    while (lo < hi) {
        long long mid = lo + (hi - lo) / 2, cur = 0;
        int students = 1;
        for (long long x : p) {
            if (cur + x > mid) {
                students++;
                cur = 0;
            }
            cur += x;
        }
        if (students <= m) hi = mid;
        else lo = mid + 1;
    }
    cout << lo << "\n";
    return 0;
}

Python solution

import sys

data = list(map(int, sys.stdin.read().split()))
n, m = data[0], data[1]
p = data[2 : 2 + n]


def students_needed(limit):
    students, cur = 1, 0
    for x in p:
        if cur + x > limit:
            students += 1
            cur = 0
        cur += x
    return students


if m > n:
    print(-1)
else:
    lo, hi = max(p), sum(p)
    while lo < hi:
        mid = (lo + hi) // 2
        if students_needed(mid) <= m:
            hi = mid
        else:
            lo = mid + 1
    print(lo)

Java solution

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt();
        long[] p = new long[n];
        long lo = 0, hi = 0;
        for (int i = 0; i < n; i++) {
            p[i] = sc.nextLong();
            lo = Math.max(lo, p[i]);
            hi += p[i];
        }
        if (m > n) {
            System.out.println(-1);
            return;
        }
        while (lo < hi) {
            long mid = lo + (hi - lo) / 2, cur = 0;
            int students = 1;
            for (long x : p) {
                if (cur + x > mid) {
                    students++;
                    cur = 0;
                }
                cur += x;
            }
            if (students <= m) hi = mid;
            else lo = mid + 1;
        }
        System.out.println(lo);
    }
}

Solve Book Allocation online · All practice problems