How should I practice Minimum Time for Dependent Tasks With Limited CPUs?

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

Is Minimum Time for Dependent Tasks With Limited CPUs associated with Google?

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

Minimum Time for Dependent Tasks With Limited CPUs

Google● HardFULLTIMEONSITE INTERVIEW

Learn

Problem statement

There are n = durations.length tasks, numbered from 0 to n - 1. Task i requires durations[i] time units. Each pair [before, after] in dependencies means task after may start only after task before has finished. The dependency graph is acyclic.

You have exactly cpuCount identical CPUs. Complete every task under these rules:

Time begins at 0. Tasks have no release times beyond their prerequisites.
Each CPU executes at most one task at a time. Once started, a task runs continuously on one CPU for its entire duration; it cannot be paused or split across CPUs.
A task starts only after all of its prerequisites have finished.
A CPU becomes free immediately when its current task finishes. A successor may start at that same instant, and simultaneous completions all take effect together.
You may deliberately leave a CPU idle, even when a task is ready, if that leads to an earlier overall finish.

Return the minimum possible time when every task is complete, measured from time 0. Return only this integer finish time, not a schedule. With one CPU, the answer is the sum of all task durations.

Function

minimumCompletionTime(durations: int[], dependencies: int[][], cpuCount: int) → int

Examples

Example 1

durations = [3,2,4]dependencies = [[0,2],[1,2]]cpuCount = 2return = 7

Run task 0 during [0,3) and task 1 during [0,2) on different CPUs. Task 2 starts at 3 after both prerequisites finish, then ends at 7. The dependency path 0 -> 2 requires 7 units, so this is optimal.

Example 2

durations = [1,3,1,1,3]dependencies = [[0,2],[0,3],[2,4],[3,4]]cpuCount = 2return = 5

Start only task 0 at time 0, leaving the other CPU idle. At time 1, run tasks 2 and 3 together until time 2. Then run tasks 1 and 4 together until time 5. The path 0 -> 2 -> 4 requires 5 units. Starting both initially ready tasks 0 and 1 immediately prevents this overlap and gives a best finish time of 6.

Example 3

durations = [2,5,3,4]dependencies = [[0,1],[0,2],[2,3]]cpuCount = 1return = 14

With one CPU, every task must run sequentially. The order 0,1,2,3 respects all dependencies and takes 2 + 5 + 3 + 4 = 14 time units.

Constraints

1 <= n == durations.length <= 8.
1 <= durations[i] <= 20.
1 <= cpuCount <= n.
0 <= dependencies.length <= n * (n - 1) / 2.
Every dependency is a unique pair of distinct task IDs in [0,n), and all dependencies form a directed acyclic graph.
Invalid inputs and cyclic graphs are outside the accepted domain. The answer is at most 160.