Question bank › Dynamic Programming
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
Part of InterviewLab's verified interview question bank. We show the prompt and concepts to practise with — never a copy-paste solution.