Book Allocation Problem: Allocate Minimum Pages

63.2k
0

Given an array pages, where pages[i] represents the number of pages in the i-th book, and an integer students, allocate all books among the students. The allocation must follow these rules:

  • Each book is assigned to exactly one student.

  • Each student gets at least one book.

  • Books assigned to a student must be contiguous.

Return the minimum possible value of the maximum pages assigned to any student. If it is not possible to allocate books, return -1.

Example 1

Input: nums = [12, 34, 67, 90], students = 2

Output: 113

Explanation: We have two students. If we give the first three books to student 1 (12 + 34 + 67 = 113 pages) and the last book to student 2 (90 pages), the maximum pages assigned to a student is 113. This is the optimal contiguous division.

Example 2

Input: nums = [15, 17, 20], students = 2

Output: 32

Explanation: Giving the first two books to student 1 (15 + 17 = 32 pages) and the last book to student 2 (20 pages) makes the maximum pages read by any student 32. Any other valid division results in a higher maximum.

Brute Force Approach

The answer is a page limit. For example, testing whether 100 can be the answer means verifying whether all books can be assigned such that no student receives more than 100 pages.

The smallest possible page limit is the largest single book, because that book must be assigned to someone. The largest possible page limit is the sum of all pages, because one student could take all books.

The brute force idea is to try every page limit from the smallest possible value to the largest possible value. The first limit that allows allocation is the answer.

Algorithm

  • First, check whether the number of students is greater than the number of books. If it is, return -1, because each student must receive at least one book, making a valid allocation impossible.

  • Find the largest single book and the total number of pages. The largest book becomes the smallest possible answer, and the total pages become the largest possible answer.

  • Try every possible page limit in this range. This works because the first valid limit found in increasing order must be the minimum answer.

  • For each limit, assign books from left to right. Keep adding books to the current student while the limit is not crossed.

  • If adding a book crosses the limit, move to the next student and start that student's pages with the current book. This keeps the book order contiguous.

  • If the required number of students is not exceeded, the limit is valid.

Dry Run

Book Allocation Problem Brute Dry Run

Book Allocation Problem Brute Dry Run

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
/*
Checks whether books can be allocated
without crossing the given page limit.
*/
bool canAllocate(vector<int>& pages, int students, long long limit) {
// At least one student is needed when books exist.
int studentsUsed = 1;
// This stores pages assigned to the current student.
long long currentPages = 0;
for (int bookPages : pages) {
// Add the book to the current student
// if the page limit is still safe.
if (currentPages + bookPages <= limit) {
currentPages += bookPages;
} else {
// Otherwise, start allocation for a new student
// because the current student would cross the limit.
studentsUsed++;
currentPages = bookPages;
}
// If too many students are needed,
// this page limit cannot work.
if (studentsUsed > students) {
return false;
}
}
return true;
}
public:
/*
Finds the minimum possible maximum pages
by trying every page limit one by one.
*/
int findPages(vector<int>& pages, int students) {
int n = pages.size();
// Each student must get at least one book.
if (students > n) {
return -1;
}
// The answer cannot be smaller than the largest book.
long long minLimit = *max_element(pages.begin(), pages.end());
// The answer cannot be larger than all pages together.
long long maxLimit = accumulate(pages.begin(), pages.end(), 0LL);
for (long long limit = minLimit; limit <= maxLimit; limit++) {
// The first valid limit is the minimum
// because limits are checked in increasing order.
if (canAllocate(pages, students, limit)) {
return (int)limit;
}
}
return -1;
}
};
// Driver code starts
int main() {
vector<int> pages = {12, 34, 67, 90};
int students = 2;
Solution obj;
cout << obj.findPages(pages, students) << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N × (Sum - Max + 1)), where N is the length of the pages array, because every possible page limit (Sum - Max + 1) may need to scan all N books.

Space Complexity: O(1), because constant space is used.

Optimal Approach

The answer is the smallest maximum page limit that allows a valid allocation. Suppose a limit of 113 works. Then a limit of 114, 120, or anything larger will also work because students get more room to hold pages. Suppose a limit of 100 does not work. Then 99, 80, or anything smaller will also fail because students get even less room.

So the possible page limits form this pattern: false, false, false, true, true, true

The task is to find the first true. That means binary search can be used on the answer range from max(pages) to sum(pages).

Algorithm

  • First, return -1 if there are more students than books. This is necessary because each student must receive at least one book.

  • Set low to the largest book. This is the minimum possible limit because every book must fit inside some student's allocation.

  • Set high to the sum of all pages. This is the maximum possible limit because one student can take all books.

  • Pick mid as a possible maximum page limit and check whether books can be allocated without any student crossing mid.

  • During the check, assign books greedily from left to right. If the next book fits in the current student's limit, add it there.

  • If the next book does not fit, start a new student. This is done because books must stay contiguous, so the current book becomes the first book of the next block.

  • If mid works, move high to mid because a smaller valid limit may still exist. Otherwise, move low to mid + 1 because the current limit is too small.

  • When low and high meet, return that value because it is the smallest valid maximum page limit.

Dry Run

Book Allocation Problem Optimal Dry Run

Book Allocation Problem Optimal Dry Run

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
/*
Checks whether books can be allocated
without crossing the given page limit.
*/
bool canAllocate(vector<int>& pages, int students, long long limit) {
// At least one student is needed when books exist.
int studentsUsed = 1;
// This stores pages assigned to the current student.
long long currentPages = 0;
for (int bookPages : pages) {
// Add the book to the current student
// if the page limit is still safe.
if (currentPages + bookPages <= limit) {
currentPages += bookPages;
} else {
// Otherwise, start allocation for a new student
// because the current student would cross the limit.
studentsUsed++;
currentPages = bookPages;
}
// If too many students are needed,
// this page limit cannot work.
if (studentsUsed > students) {
return false;
}
}
return true;
}
public:
/*
Finds the minimum possible maximum pages
using binary search on the answer range.
*/
int findPages(vector<int>& pages, int students) {
int n = pages.size();
// Each student must get at least one book.
if (students > n) {
return -1;
}
// The answer cannot be smaller than the largest book.
long long low = *max_element(pages.begin(), pages.end());
// The answer cannot be larger than all pages together.
long long high = accumulate(pages.begin(), pages.end(), 0LL);
while (low < high) {
// mid is the maximum page limit being tested.
long long mid = low + (high - low) / 2;
// If mid works, try to find a smaller valid limit.
if (canAllocate(pages, students, mid)) {
high = mid;
} else {
// If mid fails, every smaller limit also fails.
low = mid + 1;
}
}
return (int)low;
}
};
// Driver code starts
int main() {
vector<int> pages = {12, 34, 67, 90};
int students = 2;
Solution obj;
cout << obj.findPages(pages, students) << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N x log2(Sum - Max + 1)), N is the length of pages array, because each binary search check scans all books once. and binary search has a possible range of 1 to Sum-Max+1.

Space Complexity: O(1), because constant space is used.

Interview follow-up Questions

If there are more students than available books, it is physically impossible to allocate at least one book to every student. In this scenario, the program immediately returns -1.

Two PointerSortingMathsBinary SearchArrays

Read Similar Blogs

Arrays

Row wise traversal

Given a matrix with N rows and M columns, print all elements row by row from left to right. Input: mat = [[1, 2, 3], [4, 5, 6]] Output: 1 2 3 4 5 6 Explanation: First row prints as 1...

61.6k
Arrays

Main Diagonal Print

Given a matrix with N rows and M columns, print all elements present on the main diagonal. tuf-examples-1 Input: mat = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] Output: 1 5 9 Explanation: Mai...

67k
Arrays

Search Element in Matrix

Given a matrix with N rows and M columns and a target value X , search for X in the matrix. Return the position of the first occurrence of X as {row, col} . Return {-1, -1} when the target value is...

98.4k
Comments0