631. Mentor Matching
A coding club has m students and m mentors. Everybody answered the same L yes/no questions, with 1 for yes and 0 for no: students[i] holds the answers of student i and mentors[j] the answers of mentor j. The compatibility of a student and a mentor is the number of questions to which both gave the same answer.
Every student must be paired with a different mentor, so the pairing is one-to-one. Return the largest possible sum of the compatibilities of all pairs. Checking all m! pairings is too slow for the biggest inputs; assign students in order and remember which mentors are taken.
Example 1
- Input:
- students = [[1,0,1],[0,0,1]]mentors = [[1,1,0],[0,0,1]]
- Output:
- 4
- Explanation:
Pair student 0 with mentor 0 (they agree on 1 question) and student 1 with mentor 1 (they agree on all 3): 1 + 3 = 4. The other pairing scores only 2 + 0 = 2.
Example 2
- Input:
- students = [[1,1]], mentors = [[0,0]]
- Output:
- 0
- Explanation:
The only pair disagrees on both questions, so the total is 0.
Example 3
- Input:
- students = [[0,1],[1,0]], mentors = [[1,0],[0,1]]
- Output:
- 4
- Explanation:
Student 0 goes with mentor 1 and student 1 with mentor 0; both pairs agree on both questions, giving 2 + 2 = 4.
Constraints
- 1 ≤
m≤ 10 (the number of students and of mentors) - 1 ≤
L≤ 8 (the length of every answer row) - Every entry is 0 or 1.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(2^m * m)
- Space
- O(2^m)