DSA
Allocate Books
Covers: Linear Search, Binary Search. Optimal — Time O(n*logn), Space O(1).
Practice Link
You are given an array arr[] of integers, where each element arr[i] represents the number of pages in the ith book. You also have an integer k representing the number of students. The task is to allocate books to each student such that:
Each student receives atleast one book. Each student is assigned a contiguous sequence of books. No book is assigned to more than one student. The objective is to minimize the maximum number of pages assigned to any student. In other words, out of all possible allocations, find the arrangement where the student who receives the most pages still has the smallest possible maximum.
Linear Search#
Intiution#
The answer (minimum of the maximum pages) lies somewhere in the range [max(arr), sum(arr)]. The lower bound is the largest single book (a student must read at least that many pages); the upper bound is the sum of all books (one student reads everything). We try every candidate value linearly and check whether it allows a valid allocation within k students. This is correct but very slow for large arrays.
- The minimum possible answer is max(arr) — a student must read at least the largest single book.
- The maximum possible answer is sum(arr) — one student reads all books.
- For each candidate pages, use a greedy countStudents helper to check if k students suffice; return the first valid value found.
cclass Solution {
public:
int countStudents(vector<int> &arr, int maxPages)
{
int numberOfStudents = 1;
long long currentPages=0;
for(int i=0;i<arr.size();i++)
{
if(currentPages + arr[i] <= maxPages){
currentPages += arr[i];
}
else{
currentPages = arr[i];
numberOfStudents++;
}
}
return numberOfStudents;
}
int findPages(vector<int> &arr, int k) {
int numberOfBooks = arr.size();
if(k>numberOfBooks)
return -1;
int low = *max_element(arr.begin(), arr.end());
int high = accumulate(arr.begin(), arr.end(), 0);
for(int pages = low; pages<=high;pages++)
{
if(countStudents(arr, pages) <= k){
return pages;
}
}
return -1;
}
};
Time complexity: O(N * (sum(arr[])-max(arr[])+1)) ~ O(n^2) --> TLE
Space Complexity: O(1)
Binary Search#
The search space [max(arr), sum(arr)] has a monotone property: if maxPages = X is feasible (can be allocated to <= k students), then any value > X is also feasible (more pages per student means fewer students needed). This monotonicity lets us binary search on the answer instead of linearly scanning. For each midpoint, the same greedy countStudents check tells us whether to go lower or higher. This replaces the linear scan of the range with O(log(sum - max)) evaluations.
class Solution {
public:
int countStudents(vector<int> &arr, int maxPages)
{
int numberOfStudents = 1;
long long currentPages=0;
for(int i=0;i<arr.size();i++)
{
if(currentPages + arr[i] <= maxPages){
currentPages += arr[i];
}
else{
currentPages = arr[i];
numberOfStudents++;
}
}
return numberOfStudents;
}
int findPages(vector<int> &arr, int k) {
int numberOfBooks = arr.size();
if(k>numberOfBooks)
return -1;
int low = *max_element(arr.begin(), arr.end());
int high = accumulate(arr.begin(), arr.end(), 0);
while(low<=high)
{
int mid = low + (high-low)/2;
int requiredStudents = countStudents(arr, mid);
if(requiredStudents <= k){
high = mid-1;
}
else
low = mid+1;
}
return low;
}
};
Time complexity: O(N * log(sum(arr[])-max(arr[])+1)) ~ O(n*logn)
Space Complexity: O(1)