Solve graph and linked list tasks

Task Scheduling with Dependencies

You are given a list of tasks, where each task is defined as a tuple (id, duration, prerequisites).

• id: A unique integer representing the task.
• duration: An integer representing the time required to complete the task.
• prerequisites: A list of task IDs that must be completed before this task can start.

Your goal is to calculate the minimum time required to complete all tasks, assuming you have an unlimited number of workers available. If a circular dependency exists, return -1.

Function Signature

def min_completion_time(tasks: List[Tuple[int, int, List[int]]]) -> int:

Constraints

• Number of tasks: 1 to 10,000.
• Task durations: 1 to 1,000.
• Circular dependencies are possible.

Example 1

Input: [(1, 3, []), (2, 2, [1]), (3, 4, [1])] Output: 7 Explanation: Task 1 (3 units) starts at time 0. Tasks 2 and 3 can start at time 3. Task 2 finishes at 3+2=5. Task 3 finishes at 3+4=7. Max time is 7.

Example 2

Input: [(1, 5, [2]), (2, 5, [1])] Output: -1 Explanation: Circular dependency detected between 1 and 2.

Edge Cases

• Disconnected graph components.
• Tasks with no prerequisites.
• Single task scenarios.