Show problems as
Classic problem #621MediumArrayHash TableGreedySortingHeap (Priority Queue)Counting

Task Scheduler

Real-world version: Press Die Cooldown
Tracked in this browser only
Read Task Scheduler on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Learn the pattern firstConstruction and Manipulation · Priority Queues, animated step by step

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 starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def least_cycles(jobs: list[str], gap: int) -> int:
Java
public int leastCycles(char[] jobs, int gap)

More on the same topics