Question

1947. Maximum Compatibility Score Sum

中文文档

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.length
• n == students[i].length == mentors[j].length
• 1 <= m, n <= 8
• students[i][k] is either 0 or 1.
• mentors[j][k] is either 0 or 1.

Solutions

Solution 1

class Solution:
  def maxCompatibilitySum(
    self, students: List[List[int]], mentors: List[List[int]]
  ) -> int:
    def dfs(i, t):
      if i == m:
        nonlocal ans
        ans = max(ans, t)
        return
      for j in range(m):
        if not vis[j]:
          vis[j] = True
          dfs(i + 1, t + g[i][j])
          vis[j] = False

    m = len(students)
    g = [[0] * m for _ in range(m)]
    for i in range(m):
      for j in range(m):
        g[i][j] = sum(a == b for a, b in zip(students[i], mentors[j]))
    vis = [False] * m
    ans = 0
    dfs(0, 0)
    return ans

class Solution {
  private int[][] g;
  private boolean[] vis;
  private int m;
  private int ans;

  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) {
          g[i][j] += students[i][k] == mentors[j][k] ? 1 : 0;
        }
      }
    }
    dfs(0, 0);
    return ans;
  }

  private void dfs(int i, int t) {
    if (i == m) {
      ans = Math.max(ans, t);
      return;
    }
    for (int j = 0; j < m; ++j) {
      if (!vis[j]) {
        vis[j] = true;
        dfs(i + 1, t + g[i][j]);
        vis[j] = false;
      }
    }
  }
}

class Solution {
public:
  int maxCompatibilitySum(vector<vector<int>>& students, vector<vector<int>>& mentors) {
    int m = students.size();
    int n = students[0].size();
    int g[m][m];
    memset(g, 0, sizeof g);
    bool vis[m];
    memset(vis, 0, sizeof vis);
    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;
    function<void(int, int)> dfs = [&](int i, int t) {
      if (i == m) {
        ans = max(ans, t);
        return;
      }
      for (int j = 0; j < m; ++j) {
        if (!vis[j]) {
          vis[j] = true;
          dfs(i + 1, t + g[i][j]);
          vis[j] = false;
        }
      }
    };
    dfs(0, 0);
    return ans;
  }
};

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 := range g {
    g[i] = make([]int, m)
    for j := range g {
      for k := 0; k < n; k++ {
        if students[i][k] == mentors[j][k] {
          g[i][j]++
        }
      }
    }
  }
  var dfs func(int, int)
  dfs = func(i, t int) {
    if i == m {
      ans = max(ans, t)
      return
    }
    for j := 0; j < m; j++ {
      if !vis[j] {
        vis[j] = true
        dfs(i+1, t+g[i][j])
        vis[j] = false
      }
    }
  }
  dfs(0, 0)
  return
}