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.
Note: Return -1 if a valid assignment is not possible, and allotment should be in contiguous order (see the explanation for better understanding).
Examples:
Input: arr[] = [12, 34, 67, 90], k = 2 Output: 113 Explanation: Allocation can be done in following ways: [12] and [34, 67, 90] Maximum Pages = 191 [12, 34] and [67, 90] Maximum Pages = 157 [12, 34, 67] and [90] Maximum Pages = 113. Therefore, the minimum of these cases is 113, which is selected as the output.
Input: arr[] = [15, 17, 20], k = 5 Output: -1 Explanation: Allocation can not be done.
Input: arr[] = [22, 23, 67], k = 1 Output: 112
Constraints:
1 <= arr.size() <= 106
1 <= arr[i] <= 103
1 <= k <= 103
Approach 01:
-
C++
-
Python
#include <vector>
#include <numeric>
#include <algorithm>
using namespace std;
class Solution {
public:
// Function to find minimum number of pages.
int findPages(vector<int>& bookPages, int numStudents) {
// Helper function to check if a given maxPages value is valid
auto isValidAllocation = [&](const vector<int>& bookPages, int numBooks, int numStudents, int maxPages) {
int studentsRequired = 1; // Start with one student
int allocatedPages = 0; // Track current page allocation for a student
// Iterate through all books
for (int pages : bookPages) {
if (pages > maxPages) {
return false; // A single book has more pages than maxPages, allocation is not possible
}
if (allocatedPages + pages > maxPages) {
studentsRequired++; // Allocate to a new student
allocatedPages = pages; // Start new allocation with current book
if (studentsRequired > numStudents) {
return false; // If students exceed numStudents, allocation is not valid
}
} else {
allocatedPages += pages; // Add book pages to current student's allocation
}
}
return true; // Allocation is valid within the constraints
};
int numBooks = bookPages.size(); // Total number of books
if (numStudents > numBooks) {
return -1; // If students exceed books, allocation is not possible
}
int minPages = *max_element(bookPages.begin(), bookPages.end()); // Minimum pages to allocate
int maxPages = accumulate(bookPages.begin(), bookPages.end(), 0); // Maximum pages to allocate
int optimalPages = -1; // Variable to store the result
// Binary search to find the minimum maximum pages
while (minPages <= maxPages) {
int midPages = (minPages + maxPages) / 2; // Midpoint of the current range
if (isValidAllocation(bookPages, numBooks, numStudents, midPages)) {
optimalPages = midPages; // Update result with the current valid allocation
maxPages = midPages - 1; // Try for a smaller maximum by reducing the range
} else {
minPages = midPages + 1; // Increase the range for a valid allocation
}
}
return optimalPages; // Return the minimum of the maximum pages
}
};
class Solution:
# Function to find minimum number of pages.
def findPages(self, bookPages, numStudents):
# Helper function to check if a given maxPages value is valid
def isValidAllocation(bookPages, numBooks, numStudents, maxPages):
studentsRequired = 1 # Start with one student
allocatedPages = 0 # Track current page allocation for a student
# Iterate through all books
for pages in bookPages:
if pages > maxPages:
return False # A single book has more pages than maxPages, allocation is not possible
if allocatedPages + pages > maxPages:
studentsRequired += 1 # Allocate to a new student
allocatedPages = pages # Start new allocation with current book
if studentsRequired > numStudents:
return False # If students exceed numStudents, allocation is not valid
else:
allocatedPages += pages # Add book pages to current student's allocation
return True # Allocation is valid within the constraints
numBooks = len(bookPages) # Total number of books
if numStudents > numBooks:
return -1 # If students exceed books, allocation is not possible
minPages = max(bookPages) # Minimum pages to allocate (at least one book with max pages)
maxPages = sum(bookPages) # Maximum pages to allocate (all books to one student)
optimalPages = -1 # Variable to store the result
# Binary search to find the minimum maximum pages
while minPages <= maxPages:
midPages = (minPages + maxPages) // 2 # Midpoint of the current range
if isValidAllocation(bookPages, numBooks, numStudents, midPages):
optimalPages = midPages # Update result with the current valid allocation
maxPages = midPages - 1 # Try for a smaller maximum by reducing the range
else:
minPages = midPages + 1 # Increase the range for a valid allocation
return optimalPages # Return the minimum of the maximum pages
Time Complexity
- Binary Search:
- The binary search is performed on the range of possible maximum pages, which is from the largest book page count to the sum of all book pages.
- Let the range of pages be \(R = \text{sum(bookPages)} – \max(bookPages)\).
- Binary search takes \(O(\log R)\) iterations.
- Allocation Validation:
- For each midpoint in the binary search, the helper function
isValidAllocationis called. - The function iterates over the array of book pages, requiring \(O(n)\) time, where \(n\) is the number of books.
- The validation is performed for every iteration of the binary search.
- Total time for allocation validation is \(O(n \cdot \log R)\).
- For each midpoint in the binary search, the helper function
- Overall Time Complexity:
The total time complexity is \(O(n \cdot \log R)\), where \(n\) is the number of books and \(R\) is the range of pages.
Space Complexity
- Input Storage:
- The array
bookPagesis passed as input and is not modified, requiring \(O(n)\) space.
- The array
- Auxiliary Variables:
- The variables
minPages,maxPages,midPages,optimalPages, and loop counters consume \(O(1)\) space. - The lambda function
isValidAllocationuses constant space for tracking variables likestudentsRequiredandallocatedPages, requiring \(O(1)\) space.
- The variables
- Overall Space Complexity:
The total space complexity is \(O(n)\), dominated by the input array.