Split Books Among Students
There are n books on a shelf in a fixed order. pages[i] is the number of pages in book i. You must split the books among k students with these rules:
- Every book goes to exactly one student.
- Each student gets a block of books that sit next to each other on the shelf. The order of the books cannot change.
- Every student gets at least one book.
The load of a student is the total number of pages they get. Choose the split so that the largest load is as small as possible, and return that largest load.
If k is greater than n, some student cannot get a book. Return -1 in that case.
Hint: if you guess a limit L, you can check in one pass if k students are enough: give books to a student until the next book would push them over L, then start a new student. The smallest L that works is the answer, and you can binary search for it.
Examples
Example 1
- Input:
- [30,15,40,25,20], 3
- Output:
- 45
Split the shelf as [30, 15], [40], [25, 20]. The loads are 45, 40 and 45, so the largest is 45. With a limit of 44, 30 and 15 cannot share a student and 25 and 20 cannot share a student, so 3 students are not enough.
Example 2
- Input:
- [12,7,9], 3
- Output:
- 12
Three books and three students, so each student gets one book. The largest load is 12.
Example 3
- Input:
- [50,60], 3
- Output:
- -1
There are only 2 books for 3 students, so one student would get nothing. The answer is -1.
Constraints
1 <= n <= 201 <= k <= 221 <= pages[i] <= 400
Run checks your code against the 3 examples. Submit checks it against all 243 tests and needs a free account. You can also try ideas in the free JavaScript or Python compiler.