Maximum Matching of Players With Trainers
MedPrompt
You are given a 0-indexed integer array players, where players[i] represents the ability of the ith player. You are also given a 0-indexed integer array trainers, where trainers[j] represents the training capacity of the jth trainer.
The ith player can match with the jth trainer if the player's ability is less than or equal to the trainer's training capacity. Additionally, the ith player can be matched with at most one trainer, and the jth trainer can be matched with at most one player.
Return the maximum number of matchings between players and trainers that satisfy these conditions.
Example 1:
Input: players = [4,7,9], trainers = [8,2,5,8]
Output: 2
Explanation:
One of the ways we can form two matchings is as follows:
- players[0] can be matched with trainers[0] since 4 <= 8.
- players[1] can be matched with trainers[3] since 7 <= 8.
It can be proven that 2 is the maximum number of matchings that can be formed.Example 2:
Input: players = [1,1,1], trainers = [10]
Output: 1
Explanation:
The trainer can be matched with any of the 3 players.
Each player can only be matched with one trainer, so the maximum answer is 1.
Constraints:
1 <= players.length, trainers.length <= 1051 <= players[i], trainers[j] <= 109
Note: This question is the same as 445: Assign Cookies.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach attempts to solve the problem by exploring every possible valid assignment of trainers to players. It uses a recursive function that, for each player, tries to match them with every available trainer who has sufficient capacity. It also considers the option of not matching the player at all. This process of generating and checking all combinations is known as backtracking.
Algorithm
- Define a recursive helper function
solve(playerIndex, usedTrainers), whereusedTrainersis a boolean array indicating which trainers are taken. - Base Case: If
playerIndexreaches the end of theplayersarray, return 0 as no more players can be matched. - Recursive Step:
- First, consider the case of not matching the current player. Recursively call
solve(playerIndex + 1, usedTrainers)to find the matches for the remaining players. - Then, iterate through all trainers. For each trainer
jthat is not yet used and hastrainers[j] >= players[playerIndex]:- Mark trainer
jas used. - Recursively call
1 + solve(playerIndex + 1, usedTrainers)to account for the current match and find matches for the rest. - Unmark trainer
j(backtrack) to explore other possibilities.
- Mark trainer
- The result for the current state is the maximum value found among all these possibilities.
- First, consider the case of not matching the current player. Recursively call
- The initial call would be
solve(0, new boolean[trainers.length]).
Walkthrough
The brute-force method is implemented using a recursive function, let's call it solve(playerIndex, usedTrainers). The playerIndex tracks the current player we are trying to match, and usedTrainers is a boolean array to keep track of which trainers have already been assigned to a player.
The function works as follows:
- Base Case: If
playerIndexis equal to the length of theplayersarray, it means we have considered all players, so we return 0. - Recursive Step: For the player at
playerIndex, we have two main choices: a. Don't match the player: We can skip the current player and move to the next one. The number of matches in this case would besolve(playerIndex + 1, usedTrainers). b. Match the player: We iterate through all the trainers. If a trainerjis not used (usedTrainers[j]is false) and their capacity is sufficient (players[playerIndex] <= trainers[j]), we can form a match. We mark the trainer as used, and recursively call for the next player:1 + solve(playerIndex + 1, usedTrainers). After the recursive call returns, we must un-mark the trainer as used (this is the 'backtracking' step) to allow this trainer to be considered for other possibilities in the search tree. - The function returns the maximum value obtained from all the explored choices.
class Solution { public int matchPlayersAndTrainers(int[] players, int[] trainers) { boolean[] usedTrainers = new boolean[trainers.length]; return solve(0, players, trainers, usedTrainers); } private int solve(int playerIndex, int[] players, int[] trainers, boolean[] usedTrainers) { if (playerIndex == players.length) { return 0; } // Option 1: Don't match the current player. int maxMatches = solve(playerIndex + 1, players, trainers, usedTrainers); // Option 2: Try to match the current player with an available trainer. for (int i = 0; i < trainers.length; i++) { if (!usedTrainers[i] && players[playerIndex] <= trainers[i]) { usedTrainers[i] = true; // Choose maxMatches = Math.max(maxMatches, 1 + solve(playerIndex + 1, players, trainers, usedTrainers)); usedTrainers[i] = false; // Unchoose (backtrack) } } return maxMatches; }}Complexity
Time
O(M! / (M-N)!) if N <= M, which is exponential. The recursion tree branches for each player and each available trainer, leading to a combinatorial explosion of states to check.
Space
O(N + M), where N is the number of players and M is the number of trainers. This is for the recursion stack depth (up to N) and the `usedTrainers` boolean array (size M).
Trade-offs
Pros
Conceptually simple and directly follows the problem's combinatorial nature.
Cons
Extremely inefficient due to its exponential time complexity.
Will result in a 'Time Limit Exceeded' (TLE) error for the constraints specified in the problem.
Redundant computations for the same subproblems.
Solutions
Solution
class Solution {public int matchPlayersAndTrainers(int[] players, int[] trainers) { Arrays.sort(players); Arrays.sort(trainers); int ans = 0; int j = 0; for (int p : players) { while (j < trainers.length && trainers[j] < p) { ++j; } if (j < trainers.length) { ++ans; ++j; } } return ans; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.