The Gateway to Computer Science Excellence

+3 votes

You are going abroad and you have to complete a number of formalities before you leave. Each task takes a full day to complete. Fortunately, you have an army of friends to help you and each task can be done by either you or any of your friends, so you can complete as many tasks as possible in parallel, on the same day.

Some tasks depend on others: for instance, you cannot purchase foreign exchange till you have bought your ticket. If task $B$ depends on task $A$, you can start $B$ only after you complete $A$. A set of tasks with no pending dependencies can be completed in parallel.

You are given a list of $n$ such tasks to be completed, where each task comes with a set of other tasks that it depends on. The set of tasks is feasible: there are no circular dependencies. You want to compute the minimum number of days needed to complete all the tasks, given the constraints.

- Model this problem formally using graphs.
- Describe an efficient algorithm for the problem and analyze the worst-case complexity of your algorithm.

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,292 answers

198,235 comments

104,918 users