The autoclave load

A sterile services department wants the gentlest autoclave setting that still clears the night's work. The trays are not the thing to search — the load is.

The problem

Surgical instruments come back in trays, trays[i] instruments in tray i. One autoclave runs the department, in cycles of a fixed length. Each set is returned intact to its own tray, so two trays never share a cycle. A cycle sterilises at most load instruments, and a tray of 3 still occupies a whole cycle at a load of 40 — the spare capacity is lost.

There are cycles cycles before the morning theatre list starts. A heavier load runs hotter and wears the instruments faster, so the department wants the smallest load that still gets everything sterile in time.

Input. trays — instruments per tray. cycles — cycles available before the list starts.

Output. The smallest load that clears every tray within cycles.

Example.

trays = [8, 15, 6, 21], cycles = 10   ->  6

At a load of 6 the trays need 2, 3, 1 and 4 cycles: exactly the budget. At 5 they need 2, 3, 2 and 5 — twelve cycles, too many.

A second example, where one extra cycle changes the answer a lot:

trays = [8, 15, 6, 21], cycles = 4   ->  21
trays = [8, 15, 6, 21], cycles = 5   ->  15

With as many cycles as trays, every tray must finish in one, so the load matches the biggest tray. One spare cycle lets that tray split in two, and the load drops to the second biggest.

Constraints.

• 1 <= len(trays) <= 10^4
• 1 <= trays[i] <= 10^9
• len(trays) <= cycles <= 10^9

Hints

Approach

Brute force

Try every load from 1 upward and count the cycles it needs. One count costs O(n) and the load runs to 10⁹, so this is O(n · max) — around 10¹³ operations.

The insight

The predicate "a load of k finishes in time" is monotone: once it is true it stays true, so the loads form a sorted row of yes/no answers you can binary search.

A bigger load never needs more cycles, since ceil(items / k) is non-increasing in k. The loads read F F F T T T and the answer is the first T. That monotonicity is the whole licence for binary search here — nothing is sorted. The bounds follow: 1 is the smallest useful load, and at max(trays) every tray takes one cycle, which cycles >= len(trays) makes enough.

Algorithm

1. Set lo = 1 and hi = max(trays).
2. While lo < hi, take mid = (lo + hi) // 2.
3. Count cycles at mid, adding ceil(items / mid) per tray.
4. If the count fits the budget, set hi = mid.
5. Otherwise mid is too small: set lo = mid + 1.
6. When the range collapses, lo is the smallest load that works.

Complexity

Time O(n log m), m the biggest tray — about 30 halvings, each an O(n) pass. Space O(1).

Solution

"""Autoclave cycle load — binary search the per-cycle load against the cycle budget."""


def cycles_needed(trays, load):
    """Cycles to sterilise every tray, never mixing two trays in one cycle."""
    return sum((items + load - 1) // load for items in trays)


def solve(trays, cycles):
    # P(load) = "everything is sterile within `cycles` cycles". A bigger load never
    # needs more cycles, so P reads False ... False True ... True.
    # Above max(trays) the extra room is wasted: a tray still costs a whole cycle.
    lo, hi = 1, max(trays)
    while lo < hi:                     # invariant: the smallest safe load is in [lo, hi]
        mid = (lo + hi) // 2
        if cycles_needed(trays, mid) <= cycles:
            hi = mid                   # mid finishes in time; nothing bigger is needed
        else:
            lo = mid + 1               # mid misses the list
    return lo

TESTS = [
    (([8, 15, 6, 21], 10), 6),
    (([8, 15, 6, 21], 4), 21),         # one cycle per tray forces the biggest tray
    (([8, 15, 6, 21], 5), 15),
    (([12], 1), 12),
    (([1000000000], 4), 250000000),    # the answer sits exactly on a division boundary
    (([7, 7, 7, 7], 4), 7),
]

Pitfalls

• Dividing without rounding up. items // load gives one cycle for a tray of 15 at a load of 8, when it needs two. Write (items + load - 1) // load.
• Setting hi = mid - 1 when mid fits can discard the answer: the load that just worked may be the smallest that does. Pair hi = mid with lo = mid + 1 and the loop still terminates.
• Starting lo at 0 makes the first division a ZeroDivisionError, and summing the trays over cycles as an upper bound is wrong: the capacity wasted at the end of each cycle means the total is not what binds.

Variants

• Dialling in the data cap — the same monotone dial, but the crossing point needs a second check before it is the answer.
• High water — the same first-true search, on a predicate read straight off the data rather than computed.