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
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.