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
- 1 ≤ n, m ≤ 10^5
- 1 ≤ pages ≤ 10^4
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
- Guess a limit L on pages per student. Can you split the books so nobody gets more than L?
- 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);
}
}