Last Updated: 30 Dec, 2020
Placment Of students
Moderate
Asked in companies
The coordinator of the placement cell has received many applications of students applying in different companies. There are M students and N companies who are offering jobs. Each student is interested in a particular number of companies for a job. Each job opening can only accept one student and a student can only have 1 job. As a placement coordinator, you want to place a maximum number of students.
Your task is to find the maximum number of students that can be placed in one of their desired jobs
The data about the set of favourable jobs are given in the form of an M * N binary matrix named ‘mat’, i.e for M students we have M rows each having N integers. Now for example if the first candidate is interested in job1 the value of mat[i][j] will be 1 otherwise it will be 0.
Note:
It is possible that a single candidate is interested in multiple jobs but he can take up only one of the job out of his favourable jobs, also there is no priority in jobs, i.e all favourable jobs are equally favourable to the candidate
Input Format:
The first line of input contains an integer ‘T’ representing the number of test cases. Then the test cases follow.
The first line of each test case contains 2 space-separated integers ‘M’ and ‘N’ which denote the number of applicants and number of jobs respectively.
The next ‘M’ lines have ‘N’ space-separated binary numbers which denote the favourable jobs of each applicant.
Output Format:
For each test case, return a single integer denoting the maximum number of applicants that got their favourable jobs
The output for each test case is in a separate line.
Note:
You do not need to print anything; it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 100
1 <= M * N <= 3000
Time Limit: 1sec
Approaches
- The key idea is to think of the problem as a bipartite graph where one side has nodes of applicants and the other side has nodes of jobs and the edges in the graph denote the relation between the jobs and candidate. (There is a directed edge between the candidate and job if the candidate wants that job.
- Lets consider the following example:
0 1 1 0 0 0
1 0 0 1 0 0
0 0 1 0 0 0
0 0 1 1 0 0
0 0 0 0 0 0
0 0 0 0 0 1
- The arrows in grey signify the ideal matches.
- But how can this be achieved?
- We can achieve this by simply doing a depth-first search from each applicant node and see if any of his preferred jobs are available or not. We can keep track of assigned jobs using an ‘assign’ array and Keep the count of the number of people who have their jobs assigned.
We can take the following approach.
- Make an array ‘assign’ which keeps track of assignment of jobs i.e what job is assigned to what person. Initially, it is -1 for all ‘N’ elements.
- Make a variable ‘jobCount’ to keep track of the number of applicants placed.
- Make all the jobs unvisited initially.
- Then we loop through all the applicants and for each applicant we check all favorable jobs for that particular applicant and if we find a job which is either not assigned or if assigned to some other applicant, the other applicant has other jobs available, we assign the current job to that applicant.
- We do this using a DFS like function that goes through the row of the current applicant and tries to assign one of his favorite jobs using the above-mentioned algorithm.
- If we are able to assign a job to the applicant we increment the value of ‘jobCount’.
- Finally, after traversing all nodes, we return the value of ‘jobCount’.