Maximum Number of Accepted Invitations to Party
Given a grid of m boys and n girls, where grid[i][j] = 1 represents that ith boy can invite girl jth girl to party. Each boy can invite only one girl and each girl can accept only one invitation. Find the most invitations that can be accepted.
Example:
Input: grid = {{1,1,1},
{1,0,1},
{0,0,1}}
Output: 3
Explanation: The invitations can be sent as follows:
=> 1st boy invites the 2nd girl.
=> 2nd boy invites the 1st girl.
=> 3rd boy invites the 3rd girl.Input: grid = {{1,0,1,0},
{1,0,0,0},
{0,0,1,0},
{1,1,1,0}}
Output: 3
Explanation: The invitations can be sent as follows:
=> 1st boy invites the 3rd girl.
=> 2nd boy invites the 1st girl.
=> 3rd boy invites no one.
=> 4th boy invites the 2nd girl.
Approach:
The solution uses the concept of maximum bipartite matching. We have to iterating over each boy and trying to find a girl that he can invite. If a boy finds a girl who hasn’t been invited yet, he invites her. If the girl has already been invited by another boy, then we recursively check if there is another girl that the other boy can invite. If yes, then the current boy invites the girl, and the other boy invites the other girl. This process is repeated until all boys have been checked.
The key idea here is to use depth-first search (DFS), we can efficiently backtrack and find alternative matches if a certain path doesn’t lead to a solution. This will makes sure that we find the maximum possible number of matches.
Steps-by-step approach:
- Create a function canInviteGirl(), which recursively checks if the current boy can invite any girl:
- It uses backtracking to explore possible combinations.
- Check if a girl is successfully invited then returns true
- otherwise, returns false.
- Create a function maximumInvitations(), which iterates through each boy.
- For each boy, calls canInviteGirl() to check if the boy can invite a girl.
- Maintains a count of successful invitations and returns the total count.
Below are the implementation of the above approach:
#include <iostream>
#include <vector>
using namespace std;
// Function to check if the current boy can invite any girl
bool canInviteGirl(vector<vector<int> >& invitationMatrix,
int totalBoys, int currentBoy,
vector<int>& girlInvitedBy,
vector<bool>& visitedBoys)
{
// If the boy has already visited, return false
if (visitedBoys[currentBoy])
return false;
// Mark the boy as visited
visitedBoys[currentBoy] = true;
// Iterate through all the girls
for (int girl = 0;
girl < invitationMatrix[currentBoy].size();
girl++) {
// If the current boy can invite the girl
if (invitationMatrix[currentBoy][girl]) {
// If the girl is not invited by any boy or the
// boy who invited the girl can invite another
// girl
if (girlInvitedBy[girl] == -1
|| canInviteGirl(
invitationMatrix, totalBoys,
girlInvitedBy[girl], girlInvitedBy,
visitedBoys)) {
// The girl is invited by the current boy
girlInvitedBy[girl] = currentBoy;
return true;
}
}
}
return false;
}
// Function to find the maximum number of invitations
int maximumInvitations(
vector<vector<int> >& invitationMatrix)
{
int totalBoys = invitationMatrix.size();
int totalGirls = invitationMatrix[0].size();
vector<int> girlInvitedBy(
totalGirls, -1); // girl[i] = which boy has invited
// the ith girl.
int totalInvitations = 0;
// For each boy, try to invite a girl
for (int boy = 0; boy < totalBoys; boy++) {
vector<bool> visitedBoys(totalBoys, false);
if (canInviteGirl(invitationMatrix, totalBoys, boy,
girlInvitedBy, visitedBoys))
totalInvitations++;
}
return totalInvitations;
}
int main()
{
// Define the invitation matrix
vector<vector<int> > invitationMatrix
= { { 1, 1, 1 }, { 1, 0, 1 }, { 0, 0, 1 } };
// Call the maximumInvitations function and store the
// result
int totalInvitations
= maximumInvitations(invitationMatrix);
// Print the result
cout << "The maximum possible number of accepted "
"invitations is: "
<< totalInvitations << endl;
return 0;
}
import java.util.Arrays;
public class Main {
// Function to check if the current boy can invite any girl
static boolean canInviteGirl(int[][] invitationMatrix, int totalBoys, int currentBoy,
int[] girlInvitedBy, boolean[] visitedBoys) {
// If the boy has already visited, return false
if (visitedBoys[currentBoy]) return false;
// Mark the boy as visited
visitedBoys[currentBoy] = true;
// Iterate through all the girls
for (int girl = 0; girl < invitationMatrix[currentBoy].length; girl++) {
// If the current boy can invite the girl
if (invitationMatrix[currentBoy][girl] == 1) {
// If the girl is not invited by any boy or the
// boy who invited the girl can invite another girl
if (girlInvitedBy[girl] == -1 || canInviteGirl(invitationMatrix, totalBoys,
girlInvitedBy[girl], girlInvitedBy, visitedBoys)) {
// The girl is invited by the current boy
girlInvitedBy[girl] = currentBoy;
return true;
}
}
}
return false;
}
// Function to find the maximum number of invitations
static int maximumInvitations(int[][] invitationMatrix) {
int totalBoys = invitationMatrix.length;
int totalGirls = invitationMatrix[0].length;
int[] girlInvitedBy = new int[totalGirls];
Arrays.fill(girlInvitedBy, -1); // girl[i] = which boy has invited the ith girl.
int totalInvitations = 0;
// For each boy, try to invite a girl
for (int boy = 0; boy < totalBoys; boy++) {
boolean[] visitedBoys = new boolean[totalBoys];
if (canInviteGirl(invitationMatrix, totalBoys, boy, girlInvitedBy, visitedBoys))
totalInvitations++;
}
return totalInvitations;
}
public static void main(String[] args) {
// Define the invitation matrix
int[][] invitationMatrix = {{1, 1, 1}, {1, 0, 1}, {0, 0, 1}};
// Call the maximumInvitations function and store the result
int totalInvitations = maximumInvitations(invitationMatrix);
// Print the result
System.out.println("The maximum possible number of accepted invitations is: " + totalInvitations);
}
}
# Function to check if the current boy can invite any girl
def canInviteGirl(invitationMatrix, totalBoys, currentBoy, girlInvitedBy, visitedBoys):
# If the boy has already visited, return False
if visitedBoys[currentBoy]:
return False
# Mark the boy as visited
visitedBoys[currentBoy] = True
# Iterate through all the girls
for girl in range(len(invitationMatrix[currentBoy])):
# If the current boy can invite the girl
if invitationMatrix[currentBoy][girl]:
# If the girl is not invited by any boy or the boy who invited the girl can invite another girl
if girlInvitedBy[girl] == -1 or canInviteGirl(invitationMatrix, totalBoys, girlInvitedBy[girl], girlInvitedBy, visitedBoys):
# The girl is invited by the current boy
girlInvitedBy[girl] = currentBoy
return True
return False
# Function to find the maximum number of invitations
def maximumInvitations(invitationMatrix):
totalBoys = len(invitationMatrix)
totalGirls = len(invitationMatrix[0])
girlInvitedBy = [-1] * totalGirls # girl[i] = which boy has invited the ith girl.
totalInvitations = 0
# For each boy, try to invite a girl
for boy in range(totalBoys):
visitedBoys = [False] * totalBoys
if canInviteGirl(invitationMatrix, totalBoys, boy, girlInvitedBy, visitedBoys):
totalInvitations += 1
return totalInvitations
# Define the invitation matrix
invitationMatrix = [[1, 1, 1], [1, 0, 1], [0, 0, 1]]
# Call the maximumInvitations function and store the result
totalInvitations = maximumInvitations(invitationMatrix)
# Print the result
print("The maximum possible number of accepted invitations is:", totalInvitations)
// Function to check if the current boy can invite any girl
function canInviteGirl(invitationMatrix, totalBoys, currentBoy, girlInvitedBy, visitedBoys) {
// If the boy has already visited, return false
if (visitedBoys[currentBoy])
return false;
// Mark the boy as visited
visitedBoys[currentBoy] = true;
// Iterate through all the girls
for (let girl = 0; girl < invitationMatrix[currentBoy].length; girl++) {
// If the current boy can invite the girl
if (invitationMatrix[currentBoy][girl]) {
// If the girl is not invited by any boy or the boy who invited the girl can invite another girl
if (girlInvitedBy[girl] === -1 || canInviteGirl(invitationMatrix, totalBoys, girlInvitedBy[girl], girlInvitedBy, visitedBoys)) {
// The girl is invited by the current boy
girlInvitedBy[girl] = currentBoy;
return true;
}
}
}
return false;
}
// Function to find the maximum number of invitations
function maximumInvitations(invitationMatrix) {
const totalBoys = invitationMatrix.length;
const totalGirls = invitationMatrix[0].length;
const girlInvitedBy = new Array(totalGirls).fill(-1); // girl[i] = which boy has invited the ith girl.
let totalInvitations = 0;
// For each boy, try to invite a girl
for (let boy = 0; boy < totalBoys; boy++) {
const visitedBoys = new Array(totalBoys).fill(false);
if (canInviteGirl(invitationMatrix, totalBoys, boy, girlInvitedBy, visitedBoys))
totalInvitations++;
}
return totalInvitations;
}
// Define the invitation matrix
const invitationMatrix = [[1, 1, 1], [1, 0, 1], [0, 0, 1]];
// Call the maximumInvitations function and store the result
const totalInvitations = maximumInvitations(invitationMatrix);
// Print the result
console.log("The maximum possible number of accepted invitations is:", totalInvitations);
Output
The maximum possible number of accepted invitations is: 3
Time complexity: O(m * n), where m is the number of boys and n is the number of girls.
Auxiliary Space: O(n)
Contact Us