0017MediumArrayBinary Search

Overnight Print Rate

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A copy shop leaves one press running through the night. stacks[i] is the number of sheets waiting in stack i, and the shift lasts hours hours.

The operator sets a single whole number rate before leaving, and it cannot be touched again. Once an hour begins, the press draws from exactly one stack and pulls at most rate sheets out of it. A stack holding fewer than rate sheets is simply emptied, and the press then sits idle until the hour is up instead of turning to another stack.

The operator would rather run the press gently, so return the smallest rate that still leaves every stack empty by the end of the shift.

The shift is never shorter than the number of stacks, so a workable rate always exists.

Examples

Example 1

Input: stacks = [15, 8, 5, 20], hours = 9
Output: 7

At 7 sheets an hour the stacks take 3, 2, 1 and 3 hours, which is 9 in total. Dialling 6 pushes the first and last stacks to 3 and 4 hours, for 10 in total, one hour past the shift.

Example 2

Input: stacks = [20, 14, 9], hours = 3
Output: 20

The shift allows exactly one hour per stack, so the press has to clear the biggest stack in a single hour and the rate cannot dip below 20.

Example 3

Input: stacks = [17], hours = 17
Output: 1

A single stack of 17 sheets fits in 17 one-sheet hours, and no smaller whole rate exists.

Constraints

1 <= stacks.length <= 10^4
stacks.length <= hours <= 10^9
1 <= stacks[i] <= 10^9

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def min_print_rate(stacks: list[int], hours: int) -> int:

Java

public int minPrintRate(int[] stacks, int hours)

The intended approach

Time O(n log M) where M is the largest stackSpace O(1)

For a fixed rate the shift length needed is the sum of the per-stack hour counts, each rounded up, and that total can only shrink as the rate grows. Feasibility is therefore monotone: every rate above the answer works and every rate below it fails, so the answer is the boundary between the two halves. Binary search the rate over 1 through the largest stack, since the largest stack always clears in one hour at that rate, and keep the smallest rate seen that fits inside the shift.

Pythonentry point: min_print_rate

def min_print_rate(stacks, hours):
    low, high = 1, max(stacks)
    while low < high:
        rate = (low + high) // 2
        needed = 0
        for sheets in stacks:
            needed += (sheets + rate - 1) // rate
            if needed > hours:
                break
        if needed <= hours:
            high = rate
        else:
            low = rate + 1
    return low

The obvious version

Walk candidate rates upward from 1 and return the first one whose rounded-up hour total fits the shift, O(M * n).

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_print_rate(stacks, hours):
    rate = 1
    while True:
        needed = 0
        for sheets in stacks:
            needed += (sheets + rate - 1) // rate
        if needed <= hours:
            return rate
        rate += 1

How this problem was checked

Reference solution executed against 14 test cases — 14 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in