Dsa
Dynamic Programming
Medium
Task Scheduling with Dependencies
You are a project manager and you want to schedule tasks based on their dependencies. Each task can take some amount of time to complete, and some tasks must be completed before others can start. Given a list of tasks with their dependencies, determine the minimum time required to complete all tasks.
Input format:
- The first line contains an integer 'n' (1 <= n <= 100), the number of tasks.
- The second line contains 'n' space-separated integers, each representing the time required to complete the respective task.
- The following lines represent the dependencies in the format 'x y', meaning task 'x' must complete before task 'y'. The input ends when a line with '0' is encountered.
Output format:
- A single integer representing the minimum time required to complete all tasks.
Example:
Input:
3
2 4 3
1 2
1 3
0
Output:
7
The total minimum time is 7, as tasks 2 and 3 depend on task 1, which takes 2 time units.
Key concepts
dynamic_programminggraphstopological_sorting
Practise this out loud — free
Start a mock interview on THIS exact question — a voice AI interviewer opens with it, pushes back like a real onsite, then hands you an instant scorecard.
🎙 Practise this question now