Scale Engineer

Maximum Matching of Players With Trainers

Med
#2194Time: 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).
Patterns
Two PointersGreedy
Algorithms
Sorting
Data structures
Array

Prompt

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 <= 105
  • 1 <= 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), where usedTrainers is a boolean array indicating which trainers are taken.
  • Base Case: If playerIndex reaches the end of the players array, 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 j that is not yet used and has trainers[j] >= players[playerIndex]:
      • Mark trainer j as 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.
    • The result for the current state is the maximum value found among all these possibilities.
  • 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:

  1. Base Case: If playerIndex is equal to the length of the players array, it means we have considered all players, so we return 0.
  2. 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 be solve(playerIndex + 1, usedTrainers). b. Match the player: We iterate through all the trainers. If a trainer j is 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.
  3. 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

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.

← Previous

Previous problem

Next →

Next problem