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.