Minimum Time to Schedule All Dependent Tasks
Inmobi operates large-scale ad campaign and data processing pipelines, where tasks often have interdependencies and varying processing times. Efficiently scheduling these tasks across a limited number of parallel processors is critical for optimizing resource utilization and minimizing overall job completion times. This problem challenges you to design an algorithm that determines the minimum time required to complete all tasks given their dependencies and the available processing capacity.
You are given a list of tasks, each with a unique ID, a processing time, and a list of task IDs that must be completed before it can start (its dependencies). You also have a fixed number of parallel processors. Your task is to implement a function that calculates the minimum total time needed to execute all tasks.
Your solution must adhere to the following:
processingTime.numProcessors at any given time.Input:
tasks: An array of Task objects. Each Task object has the following structure:
interface Task {
id: number; // A unique identifier for the task (non-negative integer)
processingTime: number; // The time required to process this task (positive integer)
dependencies: number[]; // An array of task IDs that must be completed before this task can start
}
numProcessors: A positive integer representing the number of parallel processors available.Output:
number representing the minimum total time (makespan) to complete all tasks.tasks array is empty, the function should return 0.numProcessors: numProcessors will always be at least 1.dependencies will correspond to existing tasks.Examples
Example 1
Input:
tasks = [ { id: 0, processingTime: 3, dependencies: [] }, { id: 1, processingTime: 2, dependencies: [0] } ], numProcessors = 1
Output:
5
Note:
Task 0 starts at time 0, finishes at 3. Task 1 can only start after Task 0 finishes. Task 1 starts at time 3, finishes at 3 + 2 = 5. Total time = 5.
Example 2
Input:
tasks = [ { id: 0, processingTime: 2, dependencies: [] }, { id: 1, processingTime: 3, dependencies: [] }, { id: 2, processingTime: 1, dependencies: [0, 1] } ], numProcessors = 2
Output:
4
Note:
Tasks 0 and 1 have no dependencies and can run in parallel.
max(2, 3) = 3.Example 3
Input:
tasks = [ { id: 0, processingTime: 5, dependencies: [] }, { id: 1, processingTime: 2, dependencies: [0] }, { id: 2, processingTime: 3, dependencies: [0] }, { id: 3, processingTime: 1, dependencies: [1, 2] } ], numProcessors = 2
Output:
9
Note:
max(7, 8) = 8.Constraints
1 <= tasks.length <= 10^50 <= task.id < tasks.length (Task IDs are 0-indexed and contiguous for simplicity of mapping, or can be sparse if you use a hash map for lookups)1 <= task.processingTime <= 10^40 <= task.dependencies.length < tasks.length1 <= numProcessors <= tasks.lengthprocessingTime values are integers.2 * 10^5.Loading editor...