Pattern visualizer
Book Allocation Problem
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. 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..
Binary search the page-limit, not the shelf
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.
1FUNCTION allocate(books, m)2 low <- MAX(books)3 high <- SUM(books)4 WHILE low <= high5 mid <- FLOOR((low + high) / 2)6 need <- STUDENTS_NEEDED(books, mid)7 IF need <= m8 best <- mid9 high <- mid - 110 ELSE11 low <- mid + 112 RETURN best
← / → step · space play · Home restart