Bindery day quota

The manuscripts must be bound in catalogue order, and the deadline is fixed. The only free choice is how many pages the bindery commits to per day.

The problem

A bindery has a queue of manuscripts waiting to be sewn. Their catalogue numbers run consecutively, so they must be bound in the order given — no reordering, none set aside.

Each morning the bindery sets a page quota and works down the queue until taking the next manuscript would push the day past that quota; then it stops for the day. A manuscript is never split across two days: it is sewn in one sitting or not started.

The whole queue must be bound within days working days. A high quota means overtime, so the bindery wants the smallest quota that meets the deadline. Every manuscript must be bindable, so the quota is never below the longest one.

Input. manuscripts — a list of integers, pages per manuscript, in binding order. days — the number of working days available.

Output. The smallest daily page quota that binds the whole queue within days days.

Example.

manuscripts = [120, 90, 200, 60, 150], days = 3   ->  210

At 210 the days are 120 + 90, then 200, then 60 + 150. At 209 the first day can only take 120, the rest never pair up, and the queue slips to five days.

A second example, with a day per manuscript:

manuscripts = [120, 90, 200, 60, 150], days = 5   ->  200
manuscripts = [120, 90, 200, 60, 150], days = 1   ->  620

With five days the quota only has to clear the longest manuscript. With one day it has to clear the entire queue.

Constraints.

• 1 <= len(manuscripts) <= 5 * 10^4
• 1 <= manuscripts[i] <= 500
• 1 <= days <= len(manuscripts)

Hints

Approach

Brute force

Start at the longest manuscript and raise the quota one page at a time, simulating the queue at each step. The sum can reach 2.5 · 10⁷ pages, and each simulation walks 5 · 10⁴ manuscripts, so the worst case is on the order of 10¹² steps.

The insight

With the order fixed, one greedy sweep answers "does quota q fit in days days?", and that answer is monotone in q — so binary search the quota and let the sweep be the test.

The greedy is optimal because holding back a manuscript that fits today only moves work later: any schedule can be rewritten day by day to match it without adding a day. A larger quota accepts everything a smaller one accepted, so the day count is non-increasing in q; feasibility reads F F F T T T and the target is the first true. The bounds follow: below max(manuscripts) some manuscript is never bound, and sum(manuscripts) finishes in one day.

Algorithm

1. Set lo = max(manuscripts) and hi = sum(manuscripts).
2. While lo < hi, take mid = (lo + hi) // 2.
3. Sweep the queue: keep a running page count for the current day; when the next manuscript would exceed mid, close the day and start a new one with it.
4. If the day count is at most days, set hi = mid; otherwise lo = mid + 1.
5. Return lo.

Complexity

Time O(n log S), with S the total pages — about 25 halvings, each doing one sweep of the queue. Space O(1); the sweep keeps two counters.

Solution

"""Bindery day quota — binary search on the quota, checked by a greedy in-order sweep."""


def days_needed(manuscripts, quota):
    """Days the fixed queue takes at this quota; quota >= max(manuscripts) is assumed."""
    days, today = 1, 0
    for pages in manuscripts:
        if today + pages > quota:         # today is full, so open the next day
            days += 1
            today = 0
        today += pages
    return days


def solve(manuscripts, days):
    # Below max() a manuscript can never be bound; above sum() one day suffices.
    lo, hi = max(manuscripts), sum(manuscripts)
    while lo < hi:                        # invariant: the answer lies in [lo, hi]
        mid = (lo + hi) // 2
        if days_needed(manuscripts, mid) <= days:
            hi = mid                      # mid meets the deadline; try smaller
        else:
            lo = mid + 1                  # mid is too tight
    return lo

TESTS = [
    (([120, 90, 200, 60, 150], 3), 210),
    (([120, 90, 200, 60, 150], 5), 200),
    (([120, 90, 200, 60, 150], 1), 620),
    (([300], 1), 300),
    (([10, 10, 10, 10], 2), 20),
    (([10, 10, 10, 10], 4), 10),
    (([500, 1, 1, 1], 2), 500),
]

Pitfalls

• Starting lo at 1. The sweep is then asked about a quota below the longest manuscript, and a sweep written as "if it does not fit, open a new day and put it there" gives that manuscript its own 200-page day under a 100-page quota. The schedule is called feasible and you return a quota that binds nothing.
• Closing the day on >= instead of >. A manuscript that exactly fills the quota is legal; rejecting it burns a day and moves the example answer from 210 to 211.
• Counting the first day only when it closes. Starting the counter at 0 and incrementing on each overflow undercounts by one, so a five-day schedule is reported as four and the quota comes back too low.

Variants

• Kiln shelf size — the same smallest-capacity search where items are independent, so the check is one division per item instead of an order-respecting sweep.
• Sprinkler square — searching the answer when the feasibility check is a scan over a grid.