Want to solve this problem? Login now to get access to solve the problems

Problem

Submissions

Solution

Leaderboard

Coming soon

1

Difficulty: EASY

Avg. time to solve

15 min

Success Rate

90%

Problem Statement

Suggest Edit

```
1. No need to print anything, just return the maximum number of people that can get their favourable job.
2. There is no priority in jobs , i.e all favourable jobs are equally favourable to the candidate
```

```
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 testcase 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.
```

```
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.
```

```
1 <= T <= 100
1 <= N*M <= 3000
Where ‘T’ is the number of test cases, and ‘m’*’n’ is the number of elements in the matrix
Time Limit: 1sec
```

```
2
3 2
1 0
0 1
0 0
4 4
0 0 1 1
1 1 1 1
0 0 0 1
1 0 0 0
```

```
2
4
```

```
Test Case 1:
We see that we have 3 candidates and 2 jobs.
Candidate 1 wants jobs 1 only
Candidate 2 wants job 2 only
Candidate 3 does not like any job
So, with this given arrangement, we can have that candidate 1 gets job1 and candidate 2 gets job 2. So we placed 2 candidates. Hence we return 2.
Test Case 2:
We have 4 candidates and 4 jobs
Candidate 1 wants jobs 3 or jobs 4.
Candidate 2 wants any of the 4 jobs (pretty desperate)
Candidate 3 wants only job 4
Candidate 4 wants only job 1
So with this arrangement, we can have candidate 1 with job 3, candidate 2 with job 2 candidates 3 with job 4 and candidate 4 with job 1.
Hence we placed all the candidates, hence we return 4.
```

```
2
3 4
1 1 1 1
1 1 1 1
1 1 1 1
6 6
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
```

```
3
5
```

Want to solve this problem? Login now to get access to solve the problems