Overnight restock

A night-shift packer wants to work as slowly as the deadline allows. The array in front of you is not the thing to search — the rate is.

The problem

Pallets of cartons are waiting in a warehouse. A packer works at a fixed rate of r cartons per hour, and takes one pallet at a time: within an hour they pack from a single pallet only, so a pallet of 3 cartons at rate 10 still consumes a whole hour and the leftover capacity is lost.

There are hours hours left in the shift. Find the smallest rate r that clears every pallet in time. Working slower is less tiring, so the packer wants the smallest rate that still finishes.

Input. pallets — a list of integers, cartons on each pallet. hours — hours remaining in the shift.

Output. The smallest integer rate that clears all pallets within hours.

Example.

pallets = [3, 6, 7, 11], hours = 8   ->  4

At rate 4 the pallets take 1, 2, 2 and 3 hours — 8 in total, exactly the shift. At rate 3 they take 1, 2, 3 and 4 — ten hours, too slow.

A second example, where the extra hour changes the answer:

pallets = [30, 11, 23, 4, 20], hours = 5   ->  30
pallets = [30, 11, 23, 4, 20], hours = 6   ->  23

With exactly as many hours as pallets, every pallet must finish in one hour, so the rate has to match the largest pallet.

Constraints.

• 1 <= len(pallets) <= 10^4
• 1 <= pallets[i] <= 10^9
• len(pallets) <= hours <= 10^9

Hints

Approach

Brute force

Try every rate from 1 upward, and for each one add up the hours. Checking a rate costs O(n); the rate can be as large as 10⁹, so this is O(n · max) — about 10¹³ operations. Correct, and hopelessly slow.

The insight

The predicate "rate r finishes in time" is monotone: once it becomes true it stays true, so the rates form a sorted boolean array you can binary search.

Packing faster never takes longer, so hours_needed is non-increasing in r. That makes the rates look like F F F F T T T T, and the answer is the first T. Monotonicity is the precondition binary search needs, and here it is the whole reason the technique is legal — nothing is sorted, and nothing needs to be.

The bounds matter too. Rate 1 is always safe as a lower bound. The largest pallet is a sufficient upper bound: at that rate every pallet finishes in one hour, and the constraint hours >= len(pallets) guarantees that is enough.

Algorithm

1. Set lo = 1, hi = max(pallets).
2. While lo < hi, take mid = (lo + hi) // 2.
3. Compute the hours needed at mid, summing ceil(cartons / mid) per pallet.
4. If it fits in the shift, the answer is mid or lower: set hi = mid.
5. Otherwise mid is too slow: set lo = mid + 1.
6. When the range collapses, lo is the first rate that works.

Complexity

Time O(n log m), where m is the largest pallet — about 30 iterations of the binary search, each doing one O(n) pass. Space O(1); nothing is allocated beyond a few integers.

Solution

"""Overnight restock — binary search on the packing rate."""


def hours_needed(pallets, rate):
    """Whole hours to clear every pallet at this rate, one pallet at a time."""
    return sum((cartons + rate - 1) // rate for cartons in pallets)


def solve(pallets, hours):
    # The predicate "rate r clears the shift" is monotone: if r works, r+1 works.
    # So search the rate, not the pallets.
    lo, hi = 1, max(pallets)
    while lo < hi:                        # invariant: the answer lies in [lo, hi]
        mid = (lo + hi) // 2
        if hours_needed(pallets, mid) <= hours:
            hi = mid                      # mid works; nothing faster is needed
        else:
            lo = mid + 1                  # mid is too slow
    return lo

TESTS = [
    (([3, 6, 7, 11], 8), 4),
    (([30, 11, 23, 4, 20], 5), 30),
    (([30, 11, 23, 4, 20], 6), 23),
    (([1], 1), 1),
    (([1000000000], 2), 500000000),
    (([4, 4, 4, 4], 4), 4),
]

Pitfalls

• Integer division truncates. cartons // rate gives 1 hour for a pallet of 7 at rate 4, when it needs 2. Round up with (cartons + rate - 1) // rate.
• Setting hi = mid - 1 on success loses the answer. The successful mid might be the smallest working rate, so it has to stay in the range: hi = mid. Pairing hi = mid with lo = mid + 1 is what makes the loop terminate.
• Starting lo at 0 makes the first division a ZeroDivisionError. A rate of zero packs nothing, so 1 is the real floor.
• Using sum(pallets) // hours as an upper bound is wrong: the leftover capacity within each hour means the total is not the binding constraint.

Variants

• First failing build — the same first-true search, on a predicate that is given to you rather than computed.
• Bindery day quota — the same shape, but the check must respect the order of the items.