Allocate Minimum Pages

Binary search the page-limit, not the shelf

time O(n log(sum(books)))space O(1)

The shelf is not sorted and never gets sorted — what is being searched is the ANSWER: the page-limit no student may exceed. That limit is monotonic. If every student can stay under 120 pages, they can certainly stay under 130; if 78 is impossible, so is 77. So ask 'can 3 students respect this limit?' for a candidate limit, and each answer throws away half the remaining range. The question itself is answered greedily: walk the shelf left to right, keep piling books on the current student until the next one would break the limit, then start a new student. That uses the fewest students possible for that limit, so if even it needs too many, no split can do better.

Details

Animated on: books = [10,20,30,40,50,60] pages, 3 students. Hand each student a consecutive run of books so the student who reads the MOST pages reads as few as possible.

Problem:Allocate Minimum PagesMedium

Binary search the page-limit, not the shelf

step 1 / 9

[0]

[1]

[2]

[3]

[4]

[5]

6 books, 3 students, and each student must get a CONSECUTIVE run. The answer can never be below 60 (the biggest single book has to go to somebody) and never above 210 (one student reads everything), so binary search that range of page-limits.

Pseudocode

1FUNCTION allocate(books, m)
2  low <- MAX(books)
3  high <- SUM(books)
4  WHILE low <= high
5    mid <- FLOOR((low + high) / 2)
6    need <- STUDENTS_NEEDED(books, mid)
7    IF need <= m
8      best <- mid
9      high <- mid - 1
10    ELSE
11      low <- mid + 1
12  RETURN best

← / → step · space play · Home restart

Every step in words

Show all 9 steps

6 books, 3 students, and each student must get a CONSECUTIVE run. The answer can never be below 60 (the biggest single book has to go to somebody) and never above 210 (one student reads everything), so binary search that range of page-limits.
Limit 135: greedily filling each student to the brim splits as [10,20,30,40] | [50,60] — only 2 students needed, which fits in 3. So 135 is achievable; record it and squeeze the limit down to 134 to look for something tighter.
Limit 97: greedily filling each student to the brim splits as [10,20,30] | [40,50] | [60] — only 3 students needed, which fits in 3. So 97 is achievable; record it and squeeze the limit down to 96 to look for something tighter.
Limit 78: the greedy split [10,20,30] | [40] | [50] | [60] needs 4 students, more than the 3 available — nobody may exceed 78 pages, so the work spills over. The limit is too tight; raise the floor to 79.
Limit 87: the greedy split [10,20,30] | [40] | [50] | [60] needs 4 students, more than the 3 available — nobody may exceed 87 pages, so the work spills over. The limit is too tight; raise the floor to 88.
Limit 92: greedily filling each student to the brim splits as [10,20,30] | [40,50] | [60] — only 3 students needed, which fits in 3. So 92 is achievable; record it and squeeze the limit down to 91 to look for something tighter.
Limit 89: the greedy split [10,20,30] | [40] | [50] | [60] needs 4 students, more than the 3 available — nobody may exceed 89 pages, so the work spills over. The limit is too tight; raise the floor to 90.
Limit 90: greedily filling each student to the brim splits as [10,20,30] | [40,50] | [60] — only 3 students needed, which fits in 3. So 90 is achievable; record it and squeeze the limit down to 89 to look for something tighter.
low passed high, so 90 is the smallest limit that still fits 3 students: [10,20,30] | [40,50] | [60]. One page less and the split above would have needed an extra student.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Allocate Minimum Pages in the editor All Binary Search problems Back to roadmap