There are N modules in the project. Each module (i) has completion time denoted in number of hours (Hi) and may depend on other modules. If Module x depends on Module y then one needs to complete y before x.
s Project manager, you are asked to deliver the project as early as possible.
Provide an estimation of amount of time required to complete the project.
Input Format:
First line contains T, number of test cases.
For each test case:
First line contains N, number of modules.
Next N lines, each contain:
(i) Module ID
(Hi) Number of hours it takes to complete the module
(D) Set of module ids that i depends on - integers delimited by space.
Output Format:
Output the minimum number of hours required to deliver the project.
Input:
1
5
1 5
2 6 1
3 3 2
4 2 3
5 1 3
output:
16
I know the problem is related to topological sorting.But cant get idea how to find total hours.
I thinnk the problem description is not complete (probably the fault of the problem setter). How many tasks can your team do in parallel? I’m assuming that this is unbounded.
Some hint on how to get to topological sorting:
Each module (node in the graph) should have a start time end a finish time (simply start time + time it takes to complete the module). Additionally you have the restriction, that each module can’t start before its dependencies (nodes with edges to this module are finished) are completed. Since there are no other constraints on how many modules can be done in parallel, you start greedily a soon as the last dependency has finished. So
(start time of a module)=max (finish time of its dependencies)
and a module without dependencies can have start time 0.
The answer to the question is the max of finish times over all modules in the project.
To solve these equations efficiently you can use your initial idea.
Did you read past the first paragraph? I’m assuming that the number if parallel tasks is unbounded as the problem is missing this piece of information. Then you can compute completion time along the lines following.
The maximal number of parallel tasks is of course essential for solving the problem, as different numbers will yield different results. Since this piece of information is missing, I can only guess.