⬅ Previous Topic
Aggressive Cows ProblemNext Topic ⮕
Split Array - Minimize Largest Sum⬅ Previous Topic
Aggressive Cows ProblemNext Topic ⮕
Split Array - Minimize Largest SumTopic Contents
You are given a list of N books where each book has a certain number of pages, and you have to allocate these books to M students.
Your goal is to distribute the books among students in such a way that:
The task is to minimize the maximum number of pages assigned to a student across all students.
If it is not possible to allocate the books as per the rules, return -1
.
low = max(arr)
and high = sum(arr)
.low ≤ high
, do:mid = (low + high) / 2
.mid
pages using a helper function.high = mid - 1
.low = mid + 1
.public class BookAllocator {
public static boolean isPossible(int[] arr, int m, int maxPages) {
int students = 1;
int pages = 0;
for (int i = 0; i < arr.length; i++) {
if (arr[i] > maxPages) return false;
if (pages + arr[i] > maxPages) {
students++;
pages = arr[i];
} else {
pages += arr[i];
}
}
return students <= m;
}
public static int findMinimumPages(int[] arr, int m) {
if (m > arr.length) return -1;
int low = arr[0], high = 0;
for (int pages : arr) {
low = Math.max(low, pages);
high += pages;
}
int result = -1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (isPossible(arr, m, mid)) {
result = mid;
high = mid - 1;
} else {
low = mid + 1;
}
}
return result;
}
public static void main(String[] args) {
int[] arr = {12, 34, 67, 90};
int students = 2;
int minPages = findMinimumPages(arr, students);
System.out.println("Minimum Maximum Pages: " + minPages);
}
}
Case | Time Complexity | Explanation |
---|---|---|
Best Case | O(n) | Occurs if binary search hits the correct answer in the first try, but validation still needs to check all books. |
Average Case | O(n * log(sum - max)) | Binary search over range from max(arr) to sum(arr), and for each guess, we iterate through n books. |
Worst Case | O(n * log(sum - max)) | Even in the worst case, we perform log iterations and n-time validation per iteration. |
O(1)
Explanation: Only a fixed number of variables are used. No extra space is needed.
⬅ Previous Topic
Aggressive Cows ProblemNext Topic ⮕
Split Array - Minimize Largest SumYou can support this website with a contribution of your choice.
When making a contribution, mention your name, and programguru.org in the message. Your name shall be displayed in the sponsors list.