Internships

Approach : 
 

 

• We will recursively assign internships to students if it is available and the student is interested in that particular internship.
• When we have exhausted all students or exhausted all set of internships , we check if this is the optimal assignment.

 

 

Algorithm : 

• Initialise a vector ‘visited’ of size ‘M’ to check if the internship is available or not.
• Maintain a global variable ‘curr’ initialised to ‘0’.
• Start a recursive call from applicant 1.
• Traverse from ‘i=0’ to ‘i=M-1’ over all internships :
• If current internship is available and current applicant is interested :
  • Mark ‘visited[i]’ = 1.
  • Increment ‘curr’.
  • Recur for the next applicant.
  • After the recursive call ends, mark ‘visited[i]=0’ and decrement ‘curr’.
• When we complete calls for all ‘N’ students, update ‘ans’ as max of ‘ans’ and ‘curr’.
• Return ‘ans’ as the final result.

Approach : 

• We first notice that the graph formed by constructing edges from applicants to internships is a Bipartite graph as the vertices are divided into two sets with no edges passing among themselves.

• We will apply the Hopcroft-Karp algorithm to find the maximal matching graph to optimally assign internships to applicants.
• Let the graph formed from applicants to internships be ‘G’.
• Initially we take the maximal matching ‘g’ as empty.
• We define the ‘free vertices’ as the vertices that are not part of the maximal matching ‘g’.
• Matching edges are defined as the edges that are part of the graph ‘g’, whereas non-matching edges are those which are not part of the graph ‘g’.
• Alternating path is defined as a path in which edges alternate between the matching and non-matching edges.
• Now, if there exists any path ‘p’ in the graph ‘G’ such that it starts from a free vertex and ends at a free vertex, ( defined as Augmented path ), we remove the matching edges of ‘p’ from ‘g’ and add non-matching edges of ‘p’ to ‘g’.
• We will repeat the above step until we cannot find any augmented path in the graph ‘G’.

• For the above graph :
  • The edges marked with ‘red’ are part of the maximal matching ‘g’.
  • The vertices ‘u3’ and ‘v3’ are free vertices.
  • Edges ‘u1 -> v4’ , ‘u2 -> v2’ are matching edges while ‘u0 -> v1’ , ‘u3 -> v0’ are non-matching.
  • Path ‘u1 -> v4 -> u3’ is an alternating path.
  • Path ‘u3 -> v0 -> u0 -> v1 -> u4 -> v3’ is an augmented path.
• We will find the augmented path in the maximal matching using the ‘bfs’ function implemented in the algorithm.
• This will give us a set of assignments with the maximum applicants getting internships.

Algorithm : 

• Initialise array ‘pairU’ of size ‘N’ which stores the internship assigned to applicant.
• Initialise array ‘pairV’ of size ‘M’ which stores the applicant who got internship.
• Initialise array ‘dist’ of size ‘N’ which stores the distances of applicants in paths.
  • dist[u] is one more than dist[u’] if u is next to u’ in the augmented path.
• Convert the edges ‘g’ into an adjacency list.
• Initialise ‘result’ as 0.
• Run an infinite while loop calling the ‘bfs’ function which checks if there is still an augmented path present in the matching.
  • Traverse over the applicants from ‘u=1’ to ‘u=N’ :
  • If the current vertex is free and there is an augmented path from vertex ‘u’ :
  • Increment the value of ‘result’.
• The function ‘bfs’ implements the below algorithm :
• Initialise a queue ‘Q’ and push all the free vertices in it.
• The vertices having ‘dist[u]’ as 0 are pushed to ‘Q’ and the ‘dist’ values of the rest are initialised to ‘INF’.
• Run a while loop till ‘Q’ is not empty :
  • Let the front of ‘Q’ be ‘u’.
  • Check if the current node ‘u’ is not NIL.
  • Traverse over the adjacent vertices ‘v’ of ‘u’.
  • If the ‘dist’ of ‘pairV[v]’ is INF , which means this is still unexplored, then we add it to queue ‘Q’ and update ‘dist[pairV[v]]’.
• If we finally reach the ‘NIL’ vertex then we have found an augmented path and we return ‘true’.
• Return ‘result’ as the final answer.