2410. Maximum Matching of Players With Trainers

SourceBiweekly Contest 87 Q2DifficultyMediumRating1381

Description

You are given a 0-indexed integer array players, where players[i] represents the ability of the i^th player. You are also given a 0-indexed integer array trainers, where trainers[j] represents the training capacity of the j^th trainer.

The i^th player can match with the j^th trainer if the player's ability is less than or equal to the trainer's training capacity. Additionally, the i^th player can be matched with at most one trainer, and the j^th 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 <= 10⁵
1 <= players[i], trainers[j] <= 10⁹

Note: This question is the same as 445: Assign Cookies.

Solutions

Solution 1: Greedy + Two Pointers

Thinking

Trying every pair is too slow when \(n,m \le 10^5\). A trainer who can match a weaker player can also match a stronger one, so the weakest remaining player should take the weakest trainer who is still good enough.

Sort both arrays and handle players from weakest to strongest. The trainer pointer only moves forward: skip trainers who are too weak, then take the first one who can match. Sorting determines the running time.

Sort players and trainers by ability in non-decreasing order. Pointers \(i\) and \(j\) mark the player and the trainer under consideration.

Start from the weakest player. While the trainer's capacity is below the player's ability, move \(j\) right until a trainer is strong enough or none remain. If the trainers run out, every later player is at least as strong, so matching stops and the answer is \(i\), the number already matched. Otherwise this pair matches and both pointers move forward by one. If every player is matched, return the number of players.

The time complexity is \(O(m \times \log m + n \times \log n)\), and the space complexity is \(O(\max(\log m, \log n))\), where \(m\) and \(n\) are the numbers of players and trainers, respectively.

Python3JavaC++GoTypeScriptRust

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

class Solution {
    public int matchPlayersAndTrainers(int[] players, int[] trainers) {
        Arrays.sort(players);
        Arrays.sort(trainers);
        int m = players.length, n = trainers.length;
        for (int i = 0, j = 0; i < m; ++i, ++j) {
            while (j < n && trainers[j] < players[i]) {
                ++j;
            }
            if (j == n) {
                return i;
            }
        }
        return m;
    }
}

class Solution {
public:
    int matchPlayersAndTrainers(vector<int>& players, vector<int>& trainers) {
        ranges::sort(players);
        ranges::sort(trainers);
        int m = players.size(), n = trainers.size();
        for (int i = 0, j = 0; i < m; ++i, ++j) {
            while (j < n && trainers[j] < players[i]) {
                ++j;
            }
            if (j == n) {
                return i;
            }
        }
        return m;
    }
};

func matchPlayersAndTrainers(players []int, trainers []int) int {
    sort.Ints(players)
    sort.Ints(trainers)
    m, n := len(players), len(trainers)
    for i, j := 0, 0; i < m; i, j = i+1, j+1 {
        for j < n && trainers[j] < players[i] {
            j++
        }
        if j == n {
            return i
        }
    }
    return m
}

function matchPlayersAndTrainers(players: number[], trainers: number[]): number {
    players.sort((a, b) => a - b);
    trainers.sort((a, b) => a - b);
    const [m, n] = [players.length, trainers.length];
    for (let i = 0, j = 0; i < m; ++i, ++j) {
        while (j < n && trainers[j] < players[i]) {
            ++j;
        }
        if (j === n) {
            return i;
        }
    }
    return m;
}

impl Solution {
    pub fn match_players_and_trainers(mut players: Vec<i32>, mut trainers: Vec<i32>) -> i32 {
        players.sort();
        trainers.sort();
        let mut j = 0;
        let n = trainers.len();
        for (i, &p) in players.iter().enumerate() {
            while j < n && trainers[j] < p {
                j += 1;
            }
            if j == n {
                return i as i32;
            }
            j += 1;
        }
        players.len() as i32
    }
}

Solution 2: Greedy + Two Pointers (Iterate over Trainers)

Thinking

Solution 1 still walks past trainers who are too weak for the current player, and returns early once no trainer remains. Moving the outer loop onto the trainers removes that inner scan and the early return.

Sort both arrays and go through the trainers from weakest to strongest, keeping a pointer on the weakest unmatched player. A trainer too weak for that player is too weak for everyone left, and is skipped; a trainer strong enough produces one match and the pointer advances. The pointer's final value is the answer, and the complexity is unchanged.

Sort players and trainers by ability in non-decreasing order. Pointer \(j\) marks the weakest unmatched player and starts at \(0\).

Go through the trainers from weakest to strongest. If some player is still unmatched and that player's ability does not exceed the trainer's capacity, count one match and increment \(j\). Otherwise this trainer cannot match any remaining player and is skipped. After the scan, \(j\) is the maximum number of matches.