Allocate Minimum Number of Pages
You are given an array pages of n integers, where pages[i] represents the number of pages in the i-th book, and an integer m representing the number of students.
Allocate all the books among exactly m students such that:
- Each student receives at least one book.
- Each book is allocated to exactly one student.
- Books allocated to each student must form a contiguous sequence in the given order.
- The maximum number of pages allocated to any student is minimized.
Return this minimum possible value.
If it is impossible to allocate at least one book to each student, return -1.
Example 1:
Input: pages = [12, 34, 67, 90], m = 2
Output: 113
Explanation:
Some possible contiguous allocations are:
- [12] and [34, 67, 90] → maximum = 191
- [12, 34] and [67, 90] → maximum = 157
- [12, 34, 67] and [90] → maximum = 113
Therefore, the minimum possible maximum number of pages is 113.
Example 2:
Input: pages = [15, 10, 19, 10, 5], m = 3
Output: 25
Explanation:
One optimal allocation is: [15, 10] | [19] | [10, 5]
The students receive 25, 19, and 15 pages respectively.
The maximum is 25, and no valid allocation can produce a smaller maximum.
Therefore, the answer is 25.
Now Your Turn!
Pick the correct output for the given inputInput: pages = [8, 16, 24], m = 4
Still unsure what the problem is asking ?
Let’s go through a few more examples, step by step, to make it clearer.
Constraints:
- 1 <= n <= 105
- 1 <= pages[i] <= 106
- 1 <= m <= 105