Frontend School

Minimum Time to Schedule All Dependent Tasks

DSA
hard

Minimum Time to Schedule All Dependent Tasks

Hard
Graph
Topological Sort
Priority Queue
Greedy
Scheduling
Queue

Overview

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.

What you need to do / Task

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:

  1. A task can only start if all its dependencies are met.
  2. Once a task starts on a processor, it occupies that processor for its entire processingTime.
  3. Multiple tasks can run in parallel, up to numProcessors at any given time.
  4. The goal is to find the minimum possible time when all tasks are completed.

Input & output

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:

  • A number representing the minimum total time (makespan) to complete all tasks.

Clarifications

  • Empty tasks list: If the tasks array is empty, the function should return 0.
  • numProcessors: numProcessors will always be at least 1.
  • Task IDs: Task IDs are unique and non-negative. All IDs referenced in dependencies will correspond to existing tasks.
  • Cycles: You can assume there are no cyclic dependencies among tasks (i.e., the task graph is a Directed Acyclic Graph - DAG).

Examples

1

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.

2

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.

  • At time 0, Task 0 starts on Processor 1 (finishes at 2).
  • At time 0, Task 1 starts on Processor 2 (finishes at 3).
  • Task 2 depends on both Task 0 (finishes at 2) and Task 1 (finishes at 3). Thus, Task 2 can only start at time max(2, 3) = 3.
  • At time 2, Processor 1 becomes free. At time 3, Processor 2 becomes free.
  • Task 2 starts on Processor 2 (the one that became free at 3, or Processor 1 if it waited) at time 3, finishes at 3 + 1 = 4. Total time = 4.
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:

  1. Task 0 (pt=5) starts at 0 on P1, finishes at 5.
  2. At time 5, P1 is free. Dependencies for T1 and T2 are met. Both T1 (pt=2) and T2 (pt=3) can start.
  3. T1 starts at 5 on P1, finishes at 7.
  4. T2 starts at 5 on P2, finishes at 8.
  5. T3 (pt=1) depends on T1 (finishes at 7) and T2 (finishes at 8). T3 can start at max(7, 8) = 8.
  6. At time 7, P1 is free. At time 8, P2 is free. T3 starts at 8 on P1 (or P2), finishes at 9. Total time = 9.

Constraints

Constraints & assumptions

  • 1 <= tasks.length <= 10^5
  • 0 <= 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^4
  • 0 <= task.dependencies.length < tasks.length
  • 1 <= numProcessors <= tasks.length
  • All processingTime values are integers.
  • The total number of dependencies across all tasks will not exceed 2 * 10^5.

What interviewers evaluate

  • Correctness: Does the solution correctly calculate the minimum completion time for all valid inputs, including edge cases?
  • Efficiency: Is the algorithm's time and space complexity optimal for the given constraints? (Expect a solution better than O(N^2) for time).
  • Data Structures: Appropriate selection and usage of data structures (e.g., graphs, priority queues) to manage task states and scheduling.
  • Code Quality: Clarity, readability, and maintainability of the code, including proper variable naming and modularity.

Loading editor...