How should I practice Minimum CPUs for Fixed-Duration Jobs?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Google phone screen and onsite interview problems in FastPrep.

Is Minimum CPUs for Fixed-Duration Jobs associated with Google?

FastPrep tags this as a Google phone screen and onsite interview coding practice problem when the problem catalog has that company and stage context.

Minimum CPUs for Fixed-Duration Jobs

Google● MediumINTERNNEW GRADPHONE SCREENONSITE INTERVIEW

Learn

Problem statement

You are given an array startTimes, where each value is the start time of one job, and a positive integer duration. Every job runs for exactly duration time units.

Each CPU can execute at most one job at a time. A CPU becomes available immediately when its current job ends, so a job ending at time t does not overlap a job starting at time t.

Return the minimum number of CPUs required to execute all jobs at their specified start times.

Function

minimumCpus(startTimes: int[], duration: int) → int

Examples

Example 1

startTimes = [0,1,2]duration = 2return = 2

The first two jobs overlap. At time 2, the job that started at 0 ends and its CPU can immediately run the third job, so two CPUs suffice.

Example 2

startTimes = [1,5,10]duration = 3return = 1

Each job ends before the next one starts, so one CPU can execute all three jobs.

Example 3

startTimes = [4,4,4]duration = 1return = 3

All three jobs start simultaneously, so each requires a different CPU.

Constraints

1 <= startTimes.length <= 100000.
0 <= startTimes[i] <= 1000000000.
1 <= duration <= 1000000000.