Welcome to Subscribe On Youtube

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)$.

• Java
• C++
• Python
• Go

• 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;
      }
  };
  

• 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
  
  

• 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
  }
  

All Problems

All Solutions