Kiln shelf size

A bigger kiln shelf means fewer firings and a bigger gas bill. The studio wants the smallest shelf that still gets everything fired this month.

The problem

A community pottery studio fires work in batches. Batch i holds batches[i] pots, and glazes from different batches must never share a firing, so each batch is fired alone. A shelf holding size pots clears a batch of 15 in four goes when size is 4: three full shelves and one holding three pots, with the leftover space wasted.

The gas allowance pays for firings firings in total. A larger shelf costs more to buy and to heat, so the studio wants the smallest shelf whose firing count fits the allowance. Sizes are whole pots, and the allowance is at least the number of batches, so some shelf always works.

Input. batches — a list of integers, pots in each batch. firings — an integer, the number of firings the allowance covers.

Output. The smallest shelf size, in pots, whose total firing count is at most firings.

Example.

batches = [9, 4, 15, 2], firings = 10   ->  4

A shelf of 4 needs 3 + 1 + 4 + 1 = 9 firings, inside the allowance. A shelf of 3 needs 3 + 2 + 5 + 1 = 11, one over.

A second example, with the allowance squeezed down to one firing per batch:

batches = [9, 4, 15, 2], firings = 4   ->  15

Every batch must clear in one firing, so the shelf matches the largest batch.

Constraints.

• 1 <= len(batches) <= 5 * 10^4
• 1 <= batches[i] <= 10^6
• len(batches) <= firings <= 10^6

Hints

Approach

Brute force

Try shelf sizes 1, 2, 3, … and stop at the first that fits. Each count costs O(n), the size reaches 10⁶ and there can be 5 · 10⁴ batches: about 5 · 10¹⁰ divisions.

The insight

Total firings never increase as the shelf grows, so "this shelf fits the allowance" is a monotone predicate — false, false, …, true, true — and the answer is the first true.

For one batch, ceil(pots / size) is non-increasing in size: a bigger shelf never needs more goes. A sum of non-increasing terms is non-increasing, so the predicate flips exactly once over the whole range of sizes. That single flip is what binary search needs; the batch list itself is never sorted and never has to be.

Algorithm

1. Set lo = 1 and hi = max(batches).
2. While lo < hi, take mid = (lo + hi) // 2.
3. Count firings at mid: the sum of ceil(pots / mid) over the batches.
4. If that is at most firings, keep mid as a candidate with hi = mid; otherwise mid is too small, so lo = mid + 1.
5. When the range collapses, lo is the smallest shelf that fits.

Complexity

Time O(n log m), m being the largest batch — about 20 halvings, each one pass over the batches. Space O(1); two bounds and a running count.

Solution

"""Kiln shelf size — binary search on the smallest shelf that fits the gas allowance."""


def firings_needed(batches, size):
    """Firings when each batch is fired alone, rounding a part-full shelf up."""
    return sum((pots + size - 1) // size for pots in batches)


def solve(batches, firings):
    # firings_needed is non-increasing in size, so the predicate flips once.
    lo, hi = 1, max(batches)
    while lo < hi:                        # invariant: the answer lies in [lo, hi]
        mid = (lo + hi) // 2
        if firings_needed(batches, mid) <= firings:
            hi = mid                      # mid fits; nothing larger is needed
        else:
            lo = mid + 1                  # mid is too small
    return lo

TESTS = [
    (([9, 4, 15, 2], 10), 4),
    (([9, 4, 15, 2], 4), 15),
    (([44], 2), 22),
    (([44], 1), 44),
    (([6, 6, 6], 3), 6),
    (([6, 6, 6], 6), 3),
    (([1, 1, 1, 1], 4), 1),
    (([1000000, 999999], 3), 999999),
]

Pitfalls

• Rounding down. pots // size says a batch of 15 needs 3 firings on a shelf of 4, hiding three pots. Round up with (pots + size - 1) // size, or the count comes out low and you return a shelf that cannot do the job.
• Starting lo at 0. A shelf of zero pots divides by zero on the first probe. The smallest meaningful shelf is 1.
• Writing hi = mid - 1 after a success. That mid may be the answer, and discarding it returns a shelf one pot too small. Pair hi = mid with lo = mid + 1: the range keeps the answer and still shrinks every step.

Variants

• Bindery day quota — the same search with the items forced into order, so the check becomes a greedy sweep.
• Sprinkler square — the answer searched again, with the check itself the expensive part.