Practice/Google/Leetcode 2050. Parallel Courses III

Leetcode 2050. Parallel Courses III

CodingMust

Problem

You are managing a project with n tasks numbered from 1 to n. Each task has a specific duration given in the durations array (1-indexed), where durations[i-1] represents the time required to complete task i.

Some tasks have prerequisite dependencies: task a must be completed before task b can start. These dependencies are provided as pairs in the dependencies array, where each pair [a, b] means task a must finish before task b can begin.

Multiple tasks can be executed in parallel if their prerequisites are satisfied. Your goal is to determine the minimum total time required to complete all tasks in the project.

Requirements

1. Calculate the earliest possible completion time for all tasks
2. Tasks can run simultaneously when prerequisites are met
3. A task can only start after all its prerequisites have completed
4. Return the minimum time as an integer

Constraints

• 1 ≤ n ≤ 50,000
• 0 ≤ dependencies.length ≤ 50,000
• dependencies[i].length == 2
• 1 ≤ durations[i] ≤ 10,000
• All prerequisite relationships form a valid directed acyclic graph (no cycles)
• 1 ≤ a, b ≤ n in each dependency pair [a, b]

Examples

Example 1:

` Input: n = 3, dependencies = [[1, 3], [2, 3]], durations = [3, 2, 5] Output: 8 Explanation:

• Task 1 starts at time 0, finishes at time 3
• Task 2 starts at time 0, finishes at time 2
• Task 3 can only start when both tasks 1 and 2 are done (time 3)
• Task 3 finishes at time 3 + 5 = 8 `

Example 2:

Input: n = 1, dependencies = [], durations = [10] Output: 10 Explanation: Single task with no dependencies completes in 10 time units.

Example 3:

Input: n = 4, dependencies = [], durations = [5, 3, 8, 2] Output: 8 Explanation: All tasks are independent and run in parallel. The project completes when the longest task (duration 8) finishes.