# Maximum Matching of Players With Trainers
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-matching-of-players-with-trainers)
Canonical: https://scaleengineer.com/dsa/problems/maximum-matching-of-players-with-trainers
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers), [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
---
## Problem
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.](https://leetcode.com/problems/assign-cookies/description/)

# Approaches
## Brute-Force with Backtracking
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.
**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).
**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.
### Explanation
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.

```java
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;
    }
}
```
### 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])`.

## Dynamic Programming with Memoization
A better approach than brute-force is to use dynamic programming with memoization. By identifying overlapping subproblems in the recursive structure, we can store their results to avoid redundant calculations. To enable this, we must first sort both the `players` and `trainers` arrays. The state of our DP can be defined by `(i, j)`, representing the maximum matches possible considering players from index `i` onwards and trainers from index `j` onwards.
**Time:** O(N * M + N log N + M log M). Sorting takes O(N log N + M log M). The DP calculation involves filling an N x M table, where each state computation is O(1). · **Space:** O(N * M) for the memoization table, plus O(N + M) for the recursion stack in the worst case.
**Pros:** Guarantees the optimal solution.; Significantly more efficient than the brute-force approach.; Can solve the problem for moderate constraints.
**Cons:** The O(N * M) time and space complexity make it too slow and memory-intensive for the given constraints (N, M up to 10^5).
### Explanation
This method refines the recursive approach by adding a memory component. After sorting both arrays, a subproblem can be uniquely identified by the current indices `i` and `j` for the `players` and `trainers` arrays, respectively.

Let `dp(i, j)` be the maximum number of matches we can form from the subarray `players[i...]` and `trainers[j...]`.

The recurrence relation is defined as follows:
- **Base Case:** If we run out of players (`i == players.length`) or trainers (`j == trainers.length`), no more matches can be made. So, `dp(i, j) = 0`.
- **Recursive Step:** When considering `players[i]` and `trainers[j]`:
  - If `players[i] > trainers[j]`: The trainer `trainers[j]` is not strong enough for `players[i]`. Since the arrays are sorted, this trainer is also not strong enough for any subsequent player `players[k]` where `k > i`. Thus, we have no choice but to skip this trainer and move to the next one. The solution is `dp(i, j+1)`.
  - If `players[i] <= trainers[j]`: We have a choice.
    1.  **Match them:** We pair `players[i]` with `trainers[j]`, gaining 1 match. We then proceed to find matches for the next player and the next trainer: `1 + dp(i+1, j+1)`.
    2.  **Don't match them:** We can skip `trainers[j]` and try to match `players[i]` with a later, potentially more suitable trainer. The solution in this case is `dp(i, j+1)`.
    We take the maximum of these two options: `max(1 + dp(i+1, j+1), dp(i, j+1))`. 

We use a 2D array `memo` to store the results of `dp(i, j)` to avoid re-computation.

```java
import java.util.Arrays;

class Solution {
    Integer[][] memo;
    public int matchPlayersAndTrainers(int[] players, int[] trainers) {
        Arrays.sort(players);
        Arrays.sort(trainers);
        memo = new Integer[players.length][trainers.length];
        return solve(0, 0, players, trainers);
    }

    private int solve(int i, int j, int[] players, int[] trainers) {
        if (i == players.length || j == trainers.length) {
            return 0;
        }
        if (memo[i][j] != null) {
            return memo[i][j];
        }

        // If current trainer is too weak, we must skip them.
        if (players[i] > trainers[j]) {
             return memo[i][j] = solve(i, j + 1, players, trainers);
        }

        // If trainer is strong enough, we have two choices:
        // 1. Match player i with trainer j.
        int match = 1 + solve(i + 1, j + 1, players, trainers);
        // 2. Skip trainer j and try to match player i with a later trainer.
        int skip = solve(i, j + 1, players, trainers);

        return memo[i][j] = Math.max(match, skip);
    }
}
```
### Algorithm
- First, sort both the `players` and `trainers` arrays in non-decreasing order.
- Create a 2D memoization table, `memo[N][M]`, to store the results of subproblems, where N and M are the lengths of the arrays.
- Define a recursive function `solve(i, j)` which computes the maximum matches for players `players[i:]` and trainers `trainers[j:]`.
- Base Case: If `i >= N` or `j >= M`, it means we've run out of players or trainers, so return 0.
- Memoization Check: If `memo[i][j]` has been computed, return the stored value.
- Recursive Step:
  - If `players[i] > trainers[j]`, the current trainer is too weak for the current player (and any subsequent, stronger players). We must skip this trainer. The result is `solve(i, j + 1)`.
  - If `players[i] <= trainers[j]`, we have two choices:
    1. Match `players[i]` with `trainers[j]`. The number of matches is `1 + solve(i + 1, j + 1)`.
    2. Don't match them. Skip `trainers[j]` and see if `players[i]` can match with a later trainer. The number of matches is `solve(i, j + 1)`.
  - The result is the maximum of these two choices.
- Store the computed result in `memo[i][j]` before returning.
- The final answer is the result of the initial call `solve(0, 0)`.

## Greedy Approach with Sorting and Two Pointers
The most efficient solution uses a greedy algorithm. The core intuition is to be as economical as possible with our resources (the trainers). By matching the weakest players with the weakest possible trainers that can accommodate them, we save the stronger trainers for the stronger players who need them. This strategy maximizes the total number of matches. The implementation involves sorting both arrays and then using a single pass with two pointers.
**Time:** O(N log N + M log M), where N and M are the number of players and trainers. Sorting the arrays is the most time-consuming part. The subsequent two-pointer scan takes only O(N + M) time. · **Space:** O(log N + log M) or O(N + M), depending on the standard library's sort implementation. This space is used by the sorting algorithm itself. The algorithm otherwise uses O(1) extra space for pointers and the counter.
**Pros:** Highly efficient, with a time complexity dominated by sorting.; Optimal and guaranteed to find the maximum number of matches.; Simple and clean implementation using two pointers.; Low space complexity.
**Cons:** The greedy choice is not always immediately obvious to prove correct.; Requires sorting, which modifies the original arrays or requires extra space for copies.
### Explanation
This approach is based on a greedy strategy. To maximize the number of pairings, it's always optimal to match the current weakest player with the weakest available trainer who is strong enough. This leaves stronger trainers available for stronger players who might require them.

Here's the step-by-step algorithm:
1.  **Sort:** Sort both the `players` and `trainers` arrays in non-decreasing order. This is crucial as it allows us to consider players and trainers in increasing order of ability/capacity.
2.  **Initialize Pointers:** Use two pointers, `i` to iterate through `players` and `j` to iterate through `trainers`. Both start at index 0. Also, initialize a `matches` counter to 0.
3.  **Iterate and Match:** Traverse both arrays simultaneously using the pointers as long as they are within bounds.
    -   Compare `players[i]` and `trainers[j]`.
    -   If `players[i] <= trainers[j]`: A match is possible. We pair them up. Since this is the weakest player we're considering, matching them with the weakest possible trainer is the best greedy choice. We increment `matches`, and since this player and trainer are now 'used', we advance both pointers (`i++`, `j++`).
    -   If `players[i] > trainers[j]`: The current trainer `trainers[j]` is not capable enough for `players[i]`. Because the `players` array is sorted, this trainer will also be too weak for any subsequent player. Therefore, `trainers[j]` cannot be matched with any of the remaining players. We discard this trainer and move to the next one by incrementing `j`, while `i` stays put, as we still need to find a suitable trainer for `players[i]`.
4.  **Return Result:** The loop continues until we run out of players or trainers. The final value of `matches` is the maximum possible.

```java
import java.util.Arrays;

class Solution {
    public int matchPlayersAndTrainers(int[] players, int[] trainers) {
        // Sort both arrays to enable the greedy strategy.
        Arrays.sort(players);
        Arrays.sort(trainers);

        int i = 0; // Pointer for players
        int j = 0; // Pointer for trainers
        int matches = 0;

        while (i < players.length && j < trainers.length) {
            // If the current player can be matched with the current trainer
            if (players[i] <= trainers[j]) {
                matches++; // We found a match
                i++;       // Move to the next player
                j++;       // Move to the next trainer
            } else {
                // The current trainer is too weak for the current player.
                // Since players are sorted, this trainer is also too weak for all subsequent players.
                // So, we move to the next trainer to find one that is capable enough.
                j++;
            }
        }

        return matches;
    }
}
```
### Algorithm
- Sort the `players` array in non-decreasing order.
- Sort the `trainers` array in non-decreasing order.
- Initialize a player pointer `i = 0`, a trainer pointer `j = 0`, and a `matches` count to 0.
- Loop while both pointers `i` and `j` are within their respective array bounds:
  - If `players[i] <= trainers[j]`:
    - This means the weakest available player can be matched with the weakest available trainer that can handle them. This is an optimal move.
    - Increment the `matches` count.
    - Move to the next player by incrementing `i`.
    - Move to the next trainer by incrementing `j`.
  - Else (if `players[i] > trainers[j]`):
    - The current trainer is too weak for the current player. Since players are sorted, this trainer is also too weak for all subsequent players.
    - We must discard this trainer and try the next one. Increment `j`.
- After the loop terminates, return the total `matches` count.

# Solutions
### Java

```java
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;
  }
}

```

### Python

```python
class Solution:
    def matchPlayersAndTrainers(self, players: List[int], trainers: List[int]) -> int: players . sort() trainers . sort() ans = j = 0 for p in players: while j < len(trainers) and trainers[j] < p: j += 1 if j < len(trainers): ans += 1 j += 1 return ans

```

### CPP

```cpp
class Solution {
public:
  int matchPlayersAndTrainers(vector<int> &players, vector<int> &trainers) {
    sort(players.begin(), players.end());
    sort(trainers.begin(), trainers.end());
    int ans = 0, j = 0;
    for (int p : players) {
      while (j < trainers.size() && trainers[j] < p) {
        ++j;
      }
      if (j < trainers.size()) {
        ++ans;
        ++j;
      }
    }
    return ans;
  }
};

```