Maximum Matching of Players With Trainers
Problem
Each players[i] is a player's ability and each trainers[j] is a trainer's capacity. A player can match a trainer when ability ≤ capacity. Every player and every trainer is used at most once. Return the maximum number of player–trainer matchings.
players = [4,7,9], trainers = [8,2,5,8]2def matchPlayersAndTrainers(players, trainers):
players.sort() # weakest players first
trainers.sort() # smallest capacities first
i = j = matched = 0
while i < len(players) and j < len(trainers):
if players[i] <= trainers[j]:
matched += 1 # this trainer can take the player
i += 1 # advance to the next player
j += 1 # and consume this trainer
else:
j += 1 # trainer too weak, try a bigger one
return matchedfunction matchPlayersAndTrainers(players, trainers) {
players.sort((a, b) => a - b); // weakest players first
trainers.sort((a, b) => a - b); // smallest capacities first
let i = 0, j = 0, matched = 0;
while (i < players.length && j < trainers.length) {
if (players[i] <= trainers[j]) {
matched++; // this trainer can take the player
i++; // advance to the next player
j++; // and consume this trainer
} else {
j++; // trainer too weak, try a bigger one
}
}
return matched;
}int matchPlayersAndTrainers(int[] players, int[] trainers) {
Arrays.sort(players); // weakest players first
Arrays.sort(trainers); // smallest capacities first
int i = 0, j = 0, matched = 0;
while (i < players.length && j < trainers.length) {
if (players[i] <= trainers[j]) {
matched++; // this trainer can take the player
i++; // advance to the next player
j++; // and consume this trainer
} else {
j++; // trainer too weak, try a bigger one
}
}
return matched;
}int matchPlayersAndTrainers(vector<int>& players, vector<int>& trainers) {
sort(players.begin(), players.end()); // weakest players first
sort(trainers.begin(), trainers.end()); // smallest capacities first
int i = 0, j = 0, matched = 0;
while (i < players.size() && j < trainers.size()) {
if (players[i] <= trainers[j]) {
matched++; // this trainer can take the player
i++; // advance to the next player
j++; // and consume this trainer
} else {
j++; // trainer too weak, try a bigger one
}
}
return matched;
}Explanation
This is a classic greedy matching solved with two pointers. After sorting both arrays ascending, we sweep a player pointer i and a trainer pointer j from left to right.
The greedy rule: always try to match the weakest unmatched player with the smallest trainer that can still hold them. If players[i] ≤ trainers[j], we make a match and advance both pointers. Otherwise the current trainer is too weak for even this weakest player, so it can help nobody — we discard it by advancing only j.
Why is this optimal? If the weakest player can be served by some trainer, using the smallest such trainer never hurts: it leaves all larger trainers free for stronger players. An exchange argument shows no other pairing yields more matches. The pointers never move backward, so each player and trainer is visited once.
Example: players = [4,7,9] sort to [4,7,9] and trainers = [8,2,5,8] sort to [2,5,8,8]. Player 4 is too big for trainer 2, fits trainer 5 (match, 1). Player 7 skips trainer 8… actually fits trainer 8 (match, 2). Player 9 exceeds the last trainer 8, so we stop with 2 matches.
This is the same problem as 455. Assign Cookies, where players are children with greed factors and trainers are cookies with sizes.