391 views
3 votes
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.

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

1 Answer

Related questions

32 votes
32 votes
5 answers
1
go_editor asked May 23, 2016
6,640 views
You have $n$ lists, each consisting of $m$ integers sorted in ascending order. Merging these lists into a single sorted list will take time:$O(nm \log m)$$O(mn \log n)$...
7 votes
7 votes
1 answer
4
go_editor asked May 23, 2016
911 views
You are given two sorted lists of integers of size $m$ and $n$. Describe a divide and conquer algorithm for computing the $k$-th smallest element in the union of the two ...