Question

1820. Maximum Number of Accepted Invitations

中文文档

Description

There are m boys and n girls in a class attending an upcoming party.

You are given an m x n integer matrix grid, where grid[i][j] equals 0 or 1. If grid[i][j] == 1, then that means the ith boy can invite the jth girl to the party. A boy can invite at most one girl, and a girl can accept at most one invitation from a boy.

Return _the maximum possible number of accepted invitations._

 

Example 1:

Input: grid = [[1,1,1],
         [1,0,1],
         [0,0,1]]
Output: 3
Explanation: The invitations are sent as follows:
- The 1st boy invites the 2nd girl.
- The 2nd boy invites the 1st girl.
- The 3rd boy invites the 3rd girl.

Example 2:

Input: grid = [[1,0,1,0],
         [1,0,0,0],
         [0,0,1,0],
         [1,1,1,0]]
Output: 3
Explanation: The invitations are sent as follows:
-The 1st boy invites the 3rd girl.
-The 2nd boy invites the 1st girl.
-The 3rd boy invites no one.
-The 4th boy invites the 2nd girl.

 

Constraints:

• grid.length == m
• grid[i].length == n
• 1 <= m, n <= 200
• grid[i][j] is either 0 or 1.

Solutions

Solution 1: Hungarian Algorithm

This problem belongs to the maximum matching problem of bipartite graphs, which is suitable for solving with the Hungarian algorithm.

The core idea of the Hungarian algorithm is to continuously start from unmatched points, look for augmenting paths, and stop when there are no augmenting paths. This gives the maximum match.

The time complexity is $O(m \times n)$.

class Solution:
  def maximumInvitations(self, grid: List[List[int]]) -> int:
    def find(i):
      for j, v in enumerate(grid[i]):
        if v and j not in vis:
          vis.add(j)
          if match[j] == -1 or find(match[j]):
            match[j] = i
            return True
      return False

    m, n = len(grid), len(grid[0])
    match = [-1] * n
    ans = 0
    for i in range(m):
      vis = set()
      ans += find(i)
    return ans

class Solution {
  private int[][] grid;
  private boolean[] vis;
  private int[] match;
  private int n;

  public int maximumInvitations(int[][] grid) {
    int m = grid.length;
    n = grid[0].length;
    this.grid = grid;
    vis = new boolean[n];
    match = new int[n];
    Arrays.fill(match, -1);
    int ans = 0;
    for (int i = 0; i < m; ++i) {
      Arrays.fill(vis, false);
      if (find(i)) {
        ++ans;
      }
    }
    return ans;
  }

  private boolean find(int i) {
    for (int j = 0; j < n; ++j) {
      if (grid[i][j] == 1 && !vis[j]) {
        vis[j] = true;
        if (match[j] == -1 || find(match[j])) {
          match[j] = i;
          return true;
        }
      }
    }
    return false;
  }
}

class Solution {
public:
  int maximumInvitations(vector<vector<int>>& grid) {
    int m = grid.size(), n = grid[0].size();
    bool vis[210];
    int match[210];
    memset(match, -1, sizeof match);
    int ans = 0;
    function<bool(int)> find = [&](int i) -> bool {
      for (int j = 0; j < n; ++j) {
        if (grid[i][j] && !vis[j]) {
          vis[j] = true;
          if (match[j] == -1 || find(match[j])) {
            match[j] = i;
            return true;
          }
        }
      }
      return false;
    };
    for (int i = 0; i < m; ++i) {
      memset(vis, 0, sizeof vis);
      ans += find(i);
    }
    return ans;
  }
};

func maximumInvitations(grid [][]int) int {
  m, n := len(grid), len(grid[0])
  var vis map[int]bool
  match := make([]int, n)
  for i := range match {
    match[i] = -1
  }
  var find func(i int) bool
  find = func(i int) bool {
    for j, v := range grid[i] {
      if v == 1 && !vis[j] {
        vis[j] = true
        if match[j] == -1 || find(match[j]) {
          match[j] = i
          return true
        }
      }
    }
    return false
  }
  ans := 0
  for i := 0; i < m; i++ {
    vis = map[int]bool{}
    if find(i) {
      ans++
    }
  }
  return ans
}