0172MediumArrayHash TableGreedySortingHeap (Priority Queue)Counting

Press Die Cooldown

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 stamping shop owns one press. During each cycle the press either runs exactly one job or stands idle for that whole cycle.

You are given jobs, a list of one-character strings, where jobs[i] is the uppercase letter engraved on the die that job i needs. Two jobs carrying the same letter need the same die, and a die must cool for gap cycles between uses: if a die runs during cycle t, the next job needing it may not run before cycle t + gap + 1. Dies with different letters are independent, and you may run the jobs in whatever order you choose.

Return the fewest cycles, idle ones included, in which the shop can finish every job.

Examples

Example 1

Input: jobs = ["P", "P", "Q", "R", "P", "Q"], gap = 2
Output: 7

One seven-cycle run that finishes everything is P, Q, R, P, Q, idle, P. Each pair of P jobs is two cycles apart or more, which respects the cooling rule.

Example 2

Input: jobs = ["T", "T", "U", "U", "V", "V", "T"], gap = 1
Output: 7

One run that never idles is T, U, T, V, T, U, V. No die is asked for in two consecutive cycles, so all seven jobs land inside seven cycles.

Example 3

Input: jobs = ["D", "E", "F", "D"], gap = 3
Output: 5

One five-cycle run is D, E, F, idle, D. The two D jobs land four cycles apart, which clears the three cycles of cooling that die needs.

Constraints

1 <= jobs.length <= 10^4
jobs[i] is a single uppercase English letter given as a one-character string
0 <= gap <= 100

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 least_cycles(jobs: list[str], gap: int) -> int:

Java

public int leastCycles(char[] jobs, int gap)

The intended approach

Time O(n)Space O(1)

Only the most demanded die can force idling. Lay out the busiest letter first: its occurrences split the run into `busiest - 1` blocks of width `gap + 1`, and the tail block holds one job per letter that ties for the busiest count. Every other job can be dropped into a hole of that skeleton, so the answer is the skeleton width unless there are so many jobs that they overflow it, in which case the press never idles and the answer is the job count.

Pythonentry point: least_cycles

def least_cycles(jobs, gap):
    # Counting the labels is O(n); everything after it is O(1). The tally holds
    # at most 26 letters, so the extra space does not grow with the input.
    tally = {}
    for label in jobs:
        tally[label] = tally.get(label, 0) + 1
    busiest = max(tally.values())
    ties = sum(1 for count in tally.values() if count == busiest)
    skeleton = (busiest - 1) * (gap + 1) + ties
    return max(len(jobs), skeleton)

The obvious version

Walk the clock one cycle at a time and always run the ready die with the most jobs left, idling when nothing is cool yet. No formula, just simulation.

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_least_cycles(jobs, gap):
    left = {}
    for label in jobs:
        left[label] = left.get(label, 0) + 1
    free_at = dict((label, 0) for label in left)
    pending = len(jobs)
    clock = 0
    while pending > 0:
        pick = None
        for label, count in left.items():
            if count > 0 and free_at[label] <= clock:
                if pick is None or count > left[pick]:
                    pick = label
        if pick is not None:
            left[pick] -= 1
            free_at[pick] = clock + gap + 1
            pending -= 1
        clock += 1
    return clock

How this problem was checked

Reference solution executed against 11 test cases — 11 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