Description
There is a survey that consists of n questions where each question's answer is either 0 (no) or 1 (yes).
The survey was given to m students numbered from 0 to m - 1 and m mentors numbered from 0 to m - 1. The answers of the students are represented by a 2D integer array students where students[i] is an integer array that contains the answers of the ith student (0-indexed). The answers of the mentors are represented by a 2D integer array mentors where mentors[j] is an integer array that contains the answers of the jth mentor (0-indexed).
Each student will be assigned to one mentor, and each mentor will have one student assigned to them. The compatibility score of a student-mentor pair is the number of answers that are the same for both the student and the mentor.
- For example, if the student's answers were
[1, 0, 1] and the mentor's answers were [0, 0, 1], then their compatibility score is 2 because only the second and the third answers are the same.
You are tasked with finding the optimal student-mentor pairings to maximize the sum of the compatibility scores.
Given students and mentors, return the maximum compatibility score sum that can be achieved.
Example 1:
Input: students = [[1,1,0],[1,0,1],[0,0,1]], mentors = [[1,0,0],[0,0,1],[1,1,0]]
Output: 8
Explanation: We assign students to mentors in the following way:
- student 0 to mentor 2 with a compatibility score of 3.
- student 1 to mentor 0 with a compatibility score of 2.
- student 2 to mentor 1 with a compatibility score of 3.
The compatibility score sum is 3 + 2 + 3 = 8.
Example 2:
Input: students = [[0,0],[0,0],[0,0]], mentors = [[1,1],[1,1],[1,1]]
Output: 0
Explanation: The compatibility score of any student-mentor pair is 0.
Constraints:
m == students.length == mentors.lengthn == students[i].length == mentors[j].length1 <= m, n <= 8students[i][k] is either 0 or 1.mentors[j][k] is either 0 or 1.
Solutions
Solution 1: Preprocessing + Backtracking
We can first preprocess the compatibility score g[i][j] between each student i and mentor j, and then use a backtracking algorithm to solve the problem.
Define a function dfs(i, s), where i represents the current student being processed, and s represents the current sum of compatibility scores.
In dfs(i, s), if i ≥ m, it means all students have been assigned, and we update the answer to max(ans, s). Otherwise, we enumerate which mentor the i-th student can be assigned to, and then recursively process the next student. During the process, we use an array vis to record which mentors have already been assigned to avoid duplicate assignments.
We call dfs(0, 0) to get the maximum compatibility score sum.
The time complexity is O(m!), and the space complexity is O(m2). Here, m is the number of students and mentors.
PythonJavaC++GoTypeScriptRustJavaScript
class Solution:
def maxCompatibilitySum(
self, students: List[List[int]], mentors: List[List[int]]
) -> int:
def dfs(i: int, s: int):
if i >= m:
nonlocal ans
ans = max(ans, s)
return
for j in range(m):
if not vis[j]:
vis[j] = True
dfs(i + 1, s + g[i][j])
vis[j] = False
ans = 0
m = len(students)
vis = [False] * m
g = [[0] * m for _ in range(m)]
for i, x in enumerate(students):
for j, y in enumerate(mentors):
g[i][j] = sum(a == b for a, b in zip(x, y))
dfs(0, 0)
return ans(code-box)
class Solution {
private int m;
private int ans;
private int[][] g;
private boolean[] vis;
public int maxCompatibilitySum(int[][] students, int[][] mentors) {
m = students.length;
g = new int[m][m];
vis = new boolean[m];
for (int i = 0; i < m; ++i) {
for (int j = 0; j < m; ++j) {
for (int k = 0; k < students[i].length; ++k) {
if (students[i][k] == mentors[j][k]) {
++g[i][j];
}
}
}
}
dfs(0, 0);
return ans;
}
private void dfs(int i, int s) {
if (i >= m) {
ans = Math.max(ans, s);
return;
}
for (int j = 0; j < m; ++j) {
if (!vis[j]) {
vis[j] = true;
dfs(i + 1, s + g[i][j]);
vis[j] = false;
}
}
}
}(code-box)
class Solution {
public:
int maxCompatibilitySum(vector<vector<int>>& students, vector<vector<int>>& mentors) {
int m = students.size();
int n = students[0].size();
vector<vector<int>> g(m, vector<int>(m));
vector<bool> vis(m);
for (int i = 0; i < m; ++i) {
for (int j = 0; j < m; ++j) {
for (int k = 0; k < n; ++k) {
g[i][j] += students[i][k] == mentors[j][k];
}
}
}
int ans = 0;
auto dfs = [&](this auto&& dfs, int i, int s) {
if (i >= m) {
ans = max(ans, s);
return;
}
for (int j = 0; j < m; ++j) {
if (!vis[j]) {
vis[j] = true;
dfs(i + 1, s + g[i][j]);
vis[j] = false;
}
}
};
dfs(0, 0);
return ans;
}
};(code-box)
func maxCompatibilitySum(students [][]int, mentors [][]int) (ans int) {
m, n := len(students), len(students[0])
g := make([][]int, m)
vis := make([]bool, m)
for i, x := range students {
g[i] = make([]int, m)
for j, y := range mentors {
for k := 0; k < n; k++ {
if x[k] == y[k] {
g[i][j]++
}
}
}
}
var dfs func(int, int)
dfs = func(i, s int) {
if i == m {
ans = max(ans, s)
return
}
for j := 0; j < m; j++ {
if !vis[j] {
vis[j] = true
dfs(i+1, s+g[i][j])
vis[j] = false
}
}
}
dfs(0, 0)
return
}(code-box)
function maxCompatibilitySum(students: number[][], mentors: number[][]): number {
let ans = 0;
const m = students.length;
const vis: boolean[] = Array(m).fill(false);
const g: number[][] = Array.from({ length: m }, () => Array(m).fill(0));
for (let i = 0; i < m; ++i) {
for (let j = 0; j < m; ++j) {
for (let k = 0; k < students[i].length; ++k) {
if (students[i][k] === mentors[j][k]) {
g[i][j]++;
}
}
}
}
const dfs = (i: number, s: number): void => {
if (i >= m) {
ans = Math.max(ans, s);
return;
}
for (let j = 0; j < m; ++j) {
if (!vis[j]) {
vis[j] = true;
dfs(i + 1, s + g[i][j]);
vis[j] = false;
}
}
};
dfs(0, 0);
return ans;
}(code-box)
impl Solution {
pub fn max_compatibility_sum(students: Vec<Vec<i32>>, mentors: Vec<Vec<i32>>) -> i32 {
let mut ans = 0;
let m = students.len();
let mut vis = vec![false; m];
let mut g = vec![vec![0; m]; m];
for i in 0..m {
for j in 0..m {
for k in 0..students[i].len() {
if students[i][k] == mentors[j][k] {
g[i][j] += 1;
}
}
}
}
fn dfs(i: usize, s: i32, m: usize, g: &Vec<Vec<i32>>, vis: &mut Vec<bool>, ans: &mut i32) {
if i >= m {
*ans = (*ans).max(s);
return;
}
for j in 0..m {
if !vis[j] {
vis[j] = true;
dfs(i + 1, s + g[i][j], m, g, vis, ans);
vis[j] = false;
}
}
}
dfs(0, 0, m, &g, &mut vis, &mut ans);
ans
}
}(code-box)
/**
* @param {number[][]} students
* @param {number[][]} mentors
* @return {number}
*/
var maxCompatibilitySum = function (students, mentors) {
let ans = 0;
const m = students.length;
const vis = Array(m).fill(false);
const g = Array.from({ length: m }, () => Array(m).fill(0));
for (let i = 0; i < m; ++i) {
for (let j = 0; j < m; ++j) {
for (let k = 0; k < students[i].length; ++k) {
if (students[i][k] === mentors[j][k]) {
g[i][j]++;
}
}
}
}
const dfs = function (i, s) {
if (i >= m) {
ans = Math.max(ans, s);
return;
}
for (let j = 0; j < m; ++j) {
if (!vis[j]) {
vis[j] = true;
dfs(i + 1, s + g[i][j]);
vis[j] = false;
}
}
};
dfs(0, 0);
return ans;
};(code-box)
