Minimum Time to Run All Jobs with a Cooldown Between Identical Jobs
Company: xAI
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
You are given a list of jobs to run on a single-core CPU, where each job is represented by an uppercase letter `'A'`–`'Z'` in an array `jobs`. Jobs of the same letter are identical instances of the same job type and each instance takes exactly **one time unit** to run.
You are also given a non-negative integer `cooldown`. Between two runs of the **same job type**, there must be at least `cooldown` time units in which the CPU is doing something else — either running a different job type or sitting **idle**.
In each time unit the CPU either runs exactly one job instance or stays idle. Jobs may be executed in **any order**.
Return the **minimum number of time units** the CPU needs to finish all jobs in `jobs`.
**Example 1:**
```
Input: jobs = ["A","A","A","B","B","B"], cooldown = 2
Output: 8
Explanation: One optimal schedule is
A -> B -> idle -> A -> B -> idle -> A -> B
Each pair of consecutive A's (and B's) is separated by 2 time units.
```
**Example 2:**
```
Input: jobs = ["A","A","A","B","B","B"], cooldown = 0
Output: 6
Explanation: With no cooldown, the jobs can run back to back in any
order, e.g. A -> A -> A -> B -> B -> B.
```
**Example 3:**
```
Input: jobs = ["A","A","A","A","A","A","B","C","D","E","F","G"], cooldown = 2
Output: 16
Explanation: One optimal schedule is
A -> B -> C -> A -> D -> E -> A -> F -> G -> A -> idle -> idle -> A -> idle -> idle -> A
```
**Constraints:**
- `1 <= jobs.length <= 10^4`
- `jobs[i]` is an uppercase English letter `'A'`–`'Z'`
- `0 <= cooldown <= 100`
Aim for a solution that runs in `O(n)` time, where `n` is the number of job instances.
Quick Answer: This question evaluates understanding of scheduling constraints, frequency analysis, and time-complexity reasoning required to minimize total execution time under per-type cooldown restrictions.
You are given a list of jobs to run on a single-core CPU, where each job is an uppercase letter 'A'-'Z' in an array `jobs`. Jobs of the same letter are identical instances of the same job type and each instance takes exactly one time unit to run.
You are also given a non-negative integer `cooldown`. Between two runs of the same job type there must be at least `cooldown` time units in which the CPU is doing something else — either running a different job type or sitting idle.
In each time unit the CPU either runs exactly one job instance or stays idle. Jobs may be executed in any order. Return the minimum number of time units the CPU needs to finish all jobs in `jobs`.
Example 1: jobs = ["A","A","A","B","B","B"], cooldown = 2 -> 8 (A B idle A B idle A B).
Example 2: jobs = ["A","A","A","B","B","B"], cooldown = 0 -> 6 (run back to back).
Example 3: jobs = ["A","A","A","A","A","A","B","C","D","E","F","G"], cooldown = 2 -> 16.
Aim for O(n) time where n is the number of job instances.
Constraints
- 1 <= jobs.length <= 10^4
- jobs[i] is an uppercase English letter 'A'-'Z'
- 0 <= cooldown <= 100
Examples
Input: (["A","A","A","B","B","B"], 2)
Expected Output: 8
Explanation: maxFreq=3 (both A and B), countMax=2. Formula = (3-1)*(2+1)+2 = 8; n=6, so answer = max(6,8) = 8. Schedule: A B idle A B idle A B.
Input: (["A","A","A","B","B","B"], 0)
Expected Output: 6
Explanation: With cooldown 0 the gap size is 0, so formula = (3-1)*1+2 = 4; n=6 dominates, answer = 6 (jobs run back to back).
Hints
- The answer depends almost entirely on the most frequent job type. Lay out that job's instances first, then see whether the other jobs and idle slots fit into the gaps.
- If the most frequent job appears maxFreq times, it splits the timeline into (maxFreq - 1) gaps, each of size cooldown. Every gap can be filled by other jobs or forced idle time.
- Formula: (maxFreq - 1) * (cooldown + 1) + countMax, where countMax is how many job types tie for the maximum frequency. But if there are so many total jobs that they overflow the gaps, no idle time is ever needed, so the answer can never be less than n — take max(n, formula).