Schedule jobs with per-type cooldowns in the fewest slots
A CI runner executes one job per time slot. Some job types are expensive to restart on the same machine (they need caches to cool down), so after a job type runs, that type must wait cooldown slots before it can run again. The runner can fill those slots with other job types, or sit idle if nothing else is ready.
Implement planJobs(jobs, cooldown), which returns a schedule that runs every job in the fewest slots possible.
planJobs(jobs, cooldown) // => Array<string | null>
jobs: an array of job type names (strings). Each entry is one run that takes exactly one slot. The order of jobs does not matter.cooldown: a non-negative integer.null for an idle slot.jobs, and nothing else appears.i < j must satisfy j - i > cooldown (at least cooldown slots in between). Different types can run in consecutive slots.[] for no jobs. Do not mutate jobs.planJobs(['build', 'build', 'build', 'test', 'test', 'lint'], 2);
// => ['build', 'test', 'lint', 'build', 'test', null, 'build'] (7 slots)
planJobs(['build', 'build', 'build', 'test', 'test', 'lint'], 0);
// => 6 slots, no idle, for example ['build', 'build', 'build', 'test', 'test', 'lint']
planJobs(['e2e', 'e2e'], 3);
// => ['e2e', null, null, null, 'e2e']
planJobs(['a', 'a', 'a', 'b', 'b', 'b'], 2);
// => ['a', 'b', null, 'a', 'b', null, 'a', 'b'] (8 slots)
planJobs(['deploy'], 5); // => ['deploy'] (no idle slots at the end)
planJobs([], 2); // => []
The tests do not compare against one fixed schedule. They check that your array has the minimum length, contains exactly the given jobs plus null idle slots, and respects the cooldown. Inputs have at most 26 distinct job types and at most about 1,000 jobs.