1064MediumArrayHash TableSimulation

How Many Days the Run of Jobs Takes

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 run of jobs reads jobs, taken strictly in the order given, and each entry names the job's kind. Days are counted from one.

On any day you may either finish the next job in the run or take the day off, but a job may only be finished when at least gap whole days have passed since the last job of the same kind was finished.

Return the fewest days the whole run takes, counting the day the last job is finished.

Examples

Example 1

Input: jobs = [1, 1], gap = 1
Output: 3

The first job goes on day one. The second is the same kind and one whole day has to pass, so day two is out and it goes on day three.

Example 2

Input: jobs = [1, 2, 3], gap = 5
Output: 3

All three jobs are of different kinds, so no wait ever bites and they go on three days running.

Example 3

Input: jobs = [4, 4, 4], gap = 2
Output: 7

The three jobs share a kind and two whole days must pass between them, so they go on days one, four and seven.

Constraints

1 <= jobs.length <= 10^5
1 <= jobs[i] <= 10^9
1 <= gap <= jobs.length

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

Java

public long taskSchedulerII(int[] jobs, int gap)

The intended approach

Time O(n) over the run's length.Space O(d) for the distinct kinds.

The jobs come in a fixed order, so the only choice is how long to wait before each one, and waiting longer than forced can never help anything later. So take each job as early as its kind allows. Walk the run keeping, for each kind seen, the day its last job was finished. The earliest a job could go is the day after the previous one; if its kind was finished within the last `gap` days, push it out to the first day past that wait instead, which is the kind's last day plus `gap` plus one. Record that day against the kind and move on. The day the last job lands on is the answer. One pass and one entry per distinct kind.

Pythonentry point: task_scheduler_i_i

def task_scheduler_i_i(jobs, gap):
    last = {}
    day = 0
    for kind in jobs:
        day += 1
        if kind in last and day - last[kind] <= gap:
            day = last[kind] + gap + 1
        last[kind] = day
    return day

The obvious version

Live the days out one at a time. Keep for each kind how many more days it must rest, count off a day, lower every kind's rest by one, and finish the next job whenever its kind is rested, otherwise take the day off. Stop once the run is done. Costs a step per day, including the idle ones, rather than one step per job.

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_task_scheduler_i_i(jobs, gap):
    rest = {}
    at = 0
    day = 0
    n = len(jobs)
    while at < n:
        day += 1
        for kind in list(rest.keys()):
            rest[kind] -= 1
            if rest[kind] <= 0:
                del rest[kind]
        kind = jobs[at]
        if kind in rest:
            continue
        rest[kind] = gap + 1
        at += 1
    return day

How this problem was checked

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