TCS MockVita Solution: Problem C

Problem : TestVita

TCS is working on a new project called "TestVita". 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.

As 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:
1. First line contains N, number of modules.
2. 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.

Constraints:

1. 1 <= T <= 10
2. 0 < N < 1000; number of modules
3. 0 < i <= N; module ID
4. 0 < Hi < 60; number of hours it takes to complete the module i
5. 0 <= |D| < N; number of dependencies
6. 0 < Dk <= N; module ID of dependencies

Sample Input

1
5
1 5
2 6 1
3 3 2
4 2 3
5 1 3

Sample Output

16

Explanation:

Module 2 depends on module 1, hence complete module 1 first
After completing module 1 we can complete module 2 and then module 3
Module 4 and 5 can be started simultaneously in parallel after module 3 is completed.
Hence the answer = 5 + 6 + 3 + 2 = 16

C++ Implementation:

#include <iostream>
#include <cstdio>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <cmath>
using namespace std;
#define MAX 100000

int findDepend(int *h,int *d,int key,int n)
{
 int max = 0;
 for(int i = 1;i<=n;i++)
 {
  if(d[i]==key)
  {
   max = h[i] > max ? h[i] : max;
  }
 }
 return max;
}

int main() {
 int t;
 cin>>t;
 while(t--)
 {
  int n;
  int mod[MAX];
  int hours[MAX];
  int depend[MAX];
  int minimum = 0;
  int max;
  cin>>n;
  cin>>mod[1]>>hours[1];
  for(int i=1;i<=n;i++)
  {
   if(depend[i]==0)
   {
    minimum = hours[i] > minimum ? hours[i] : minimum;
   }
  }
  for(int i=2;i<=n;i++)
   cin>>mod[i]>>hours[i]>>depend[i];
  for(int i=1;i<=n;i++)
  {
   int maxHours = findDepend(hours,depend,mod[i],n);
   minimum += maxHours;
  }
  cout<<minimum<<endl;
 }
 return 0;
}

Note: Some of the test cases are failing. You can contribute your own solution or can give suggestions here to help other aspirants. All you need to do is, Just paste your code down in comments or send an email to sathish@coderegister.co.in. Your code will appear in few minutes.

Other Problems from TCS Mockvita - 1 and Mockvita - 2:

Solution : MockVita-I Problem D

Solution : MockVita-II Problem C

Solution : MockVita-II Problem B

Solution : MockVita-II Problem D

Solution : MockVita-II Problem A

Solution : MockVita-I Problem B

Solution : MockVita-I Problem C

Solution : MockVita-I Problem F

Solution : MockVita-I Problem A