Binary Search : Allocate books
Binary search problem: Allocate library books with a minimum of a maximum number of pages.
Given:
N number of books are available. ( 1 . . . N )
Each book ‘x’ from 1 .. N has B [ x ] number of pages
There are ‘S’ students.
Book allocation criteria
Criteria 1 : Allocate all the books.
Criteria 2 : Each student is issued at least one book.
Criteria 3 : Allocate the books in continuous order.
Criteria 4 : Allocate the books such that the maximum number of pages of books issued to a student is minimum.
Example:
Consider 4 books with pages [ 10 , 32 , 70, 88 ]
Number of students : 2
Possible allocations as below:
Allocation 1 -> S1 : ( 10 ) S2 : ( 32 + 70 + 88 ) Max pages = 190
Allocation 2 -> S1 : ( 10 + 32 ) S2 : ( 70 + 88 ) Max pages = 158
Allocation 3 -> S1 : ( 10 + 32 + 70 ) S2 : ( 88 ) Max pages = 112
From the above 4 allocations, the minimum of max pages after the allocation is 112.
Idea for solving the book allocation problem using binary search
Case a) If the number of books is less than the number of students, then at least 1 student is not issued any book.
Case b) If the number of books equals number of students, then each student gets a book. Thus the minimum of maximum pages allocated is maximum of ( B[1], B[2], … B[N] ).
Use binary search to find the minimum of the maximum number of pages
Example :
Consider 4 books with pages [ 1, 2, 3, 4 ], and 2 students.
Choose a very large number (INT_MAX) say 100 (maxpages) that we can allocate to a student.
| Beg | End | Mid (Max Pages) | Student 1 | Student 2 | Number of students with books |
|---|---|---|---|---|---|
| 0 | 100 | 50 | 1 + 2 + 3 + 4 (All 4 books) | 0 (No books) | 1 (Student 1). More pages have got allocated to Student 1. So continue binary search with smaller number of max pages i.e (50-1) / 2 |
| 0 | 49 | 24 | 1 + 2 + 3 + 4 (All 4 books) | 0 (No books) | 1 (Student 1). More pages have got allocated to Student 1. So continue binary search with smaller number of max pages i.e 24-1 / 2 |
| 0 | 23 | 11 | 1 + 2 + 3 + 4 (All 4 books) | 0 (No books) | 1 (Student 1). More pages have got allocated to Student 1. So continue binary search with smaller number of max pages i.e 11-1 / 2 |
| 0 | 10 | 5 | 1 + 2 (2 books) | 3 + 4 (2 books) | Student 2 now has more than (Max Pages i.e 5) so try with a bigger number. |
| 6 | 10 | 8 | 1 + 2 + 3 (3 books) | 4 (1 book) | 2 (Student 1, Student 2). 8 pages is valid but still try with a lower number of max pages. |
| 6 | 7 | 6 | 1 + 2 + 3 (3 books) | 4 (1 book) | 2 (Student 1, Student 2). 6 pages is valid but still try with a lower number of max pages. |
Since beg <= end becomes invalid, the search terminates. Thus we have 6 as the minimum of maximum pages that can be allocated to a student.
Time complexity : Log ( N )
Program for allotting all the library books to N student using binary search.
def CanAllocate (books, maxpages, students) :
student_num = 1
allocated_pages = 0
for pages in (books) :
if (allocated_pages <= maxpages) :
allocated_pages += pages
# Current allocation exceeds the maxpages, so this
# allocation may go to the next student.
if (allocated_pages > maxpages) :
next_student_allocated_pages = pages
# If the next_student_allocated_pages > maxpages, then the allocation is invalid and
# cannot be done for the next student. So try with bigger page allocation (maxpages)
if (next_student_allocated_pages > maxpages) :
return False
# Allocation is valid so proceed.
student_num += 1
allocated_pages = next_student_allocated_pages
# If student number is less than total students, more pages have got allocated to
# the students. We can start with less number of pages in the next go.
# So continue the binary search
if (student_num <= students) :
return True
return False
def IssueBooks (books, students) :
# Each student should be alloted atleast 1 book.
if (len(books) < students) :
return -1
if (len(books) == students) :
return max(books)
end = 999999999
beg = 0
possible_pages = 0
while (beg <= end) :
maxpages = int(beg + (end - beg)/2)
if (CanAllocate(books, maxpages, students)) :
possible_pages = maxpages
end = maxpages - 1
else :
beg = maxpages + 1
return possible_pages
def main () :
books = [ 10, 32, 70, 88 ]
# Student(s) 1 1:(10 + 32 + 70 + 88)
# Student(s) 2 1:(10 + 32 + 70), 2:(88)
# Student(s) 3 1:(10 + 32) 2:(70), 3:(88)
# Student(s) 4 1:(10), 2:(32), 3:(70), 4:(88)
for students in range(1, 5) :
print("Maximum possible pages allocated to " + str(students) + " : " + str(IssueBooks(books, students)))
if __name__ == "__main__" :
main()
Output
Maximum possible pages allocated to 1 : 200
Maximum possible pages allocated to 2 : 112
Maximum possible pages allocated to 3 : 88
Maximum possible pages allocated to 4 : 88
#include<iostream>
#include<vector>
#include<climits>
#include<algorithm>
using namespace std;
bool CanAllocate (vector<int>& books, int& maxpages, int students) {
int student_num = 1;
int allocated_pages = 0;
for (const auto& pages : books) {
if (allocated_pages <= maxpages) {
allocated_pages += pages;
/* Current allocation exceeds the maxpages, so this
allocation may go to the next student.*/
if (allocated_pages > maxpages) {
int next_student_allocated_pages = pages;
/* If the next_student_allocated_pages > maxpages, then the allocation is invalid and
cannot be done for the next student. So try with bigger page allocation (maxpages)*/
if (next_student_allocated_pages > maxpages)
return false;
// Allocation is valid so proceed.
student_num++;
allocated_pages = next_student_allocated_pages;
}
}
}
/* If student number is less than total students, more pages have got allocated to
the students. We can start with less number of pages in the next go.
So continue the binary search */
if (student_num <= students)
return true;
return false;
}
int IssueBooks (vector<int>& books, int students) {
// Each student should be alloted atleast 1 book.
if (books.size() < students)
return -1;
if (books.size() == students)
return *max_element(books.begin(), books.end());
int end = INT_MAX;
int beg = 0;
int possible_pages = 0;
while (beg <= end) {
int maxpages = beg + (end - beg)/2;
if (CanAllocate(books, maxpages, students)) {
possible_pages = maxpages;
end = maxpages - 1;
} else {
beg = maxpages + 1;
}
}
return possible_pages;
}
int main() {
vector<int> books = {10, 32, 70, 88};
// Student(s) 1 1:(10 + 32 + 70 + 88)
// Student(s) 2 1:(10 + 32 + 70), 2:(88)
// Student(s) 3 1:(10 + 32) 2:(70), 3:(88)
// Student(s) 4 1:(10), 2:(32), 3:(70), 4:(88)
for (int students=1, students<=4; students++) {
cout << "Maximum possible pages allocated to " << students << " : " << IssueBooks(books, students) << endl;
}
return 0;
}
Output
Maximum possible pages allocated to 1 : 200
Maximum possible pages allocated to 2 : 112
Maximum possible pages allocated to 3 : 88
Maximum possible pages allocated to 4 : 88
import java.util.List;
import java.util.Collections;
import java.util.Arrays;
class AllocateBooks {
boolean CanAllocate (List<Integer> books, int maxpages, int students) {
int student_num = 1;
int allocated_pages = 0;
for (int pages : books) {
if (allocated_pages <= maxpages) {
allocated_pages += pages;
/* Current allocation exceeds the maxpages, so this
allocation may go to the next student.*/
if (allocated_pages > maxpages) {
int next_student_allocated_pages = pages;
/* If the next_student_allocated_pages > maxpages, then the allocation is invalid and
cannot be done for the next student. So try with bigger page allocation (maxpages)*/
if (next_student_allocated_pages > maxpages)
return false;
// Allocation is valid so proceed.
student_num++;
allocated_pages = next_student_allocated_pages;
}
}
}
/* If student number is less than total students, more pages have got allocated to
the students. We can start with less number of pages in the next go.
So continue the binary search */
if (student_num <= students)
return true;
return false;
}
int IssueBooks (List<Integer> books, int students) {
// Each student should be alloted atleast 1 book.
if (books.size() < students)
return -1;
if (books.size() == students)
return Collections.max(books);
int end = Integer.MAX_VALUE;
int beg = 0;
int possible_pages = 0;
while (beg <= end) {
int maxpages = beg + (end - beg)/2;
if (CanAllocate(books, maxpages, students)) {
possible_pages = maxpages;
end = maxpages - 1;
} else {
beg = maxpages + 1;
}
}
return possible_pages;
}
public static void main (String[] args) {
List<Integer> books = Arrays.asList(10, 32, 70, 88);
// Student(s) 1 1:(10 + 32 + 70 + 88)
// Student(s) 2 1:(10 + 32 + 70), 2:(88)
// Student(s) 3 1:(10 + 32) 2:(70), 3:(88)
// Student(s) 4 1:(10), 2:(32), 3:(70), 4:(88)
AllocateBooks a = new AllocateBooks();
for (int students=1; students<=4; students++) {
System.out.println("Maximum possible pages allocated to " + students + " : " + a.IssueBooks(books, students));
}
}
}
Output
Maximum possible pages allocated to 1 : 200
Maximum possible pages allocated to 2 : 112
Maximum possible pages allocated to 3 : 88
Maximum possible pages allocated to 4 : 88