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.

  1. Model this problem formally using graphs.
  2. Describe an efficient algorithm for the problem and analyze the worst-case complexity of your algorithm.
in Algorithms by Veteran (105k points) | 55 views

Please log in or register to answer this question.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,292 answers
104,918 users