2410. Maximum Matching of Players With Trainers

Problem Description

Given two arrays players and trainers, where players[i] represents the ability of the ith player and trainers[j] represents the training capacity of the jth trainer, find the maximum number of matchings between players and trainers such that the player's ability is less than or equal to the trainer's capacity. Each player and trainer can only be matched once.

Solution: Greedy Approach with Two Pointers

The optimal solution uses a greedy approach combined with two pointers. The idea is to sort both the players and trainers arrays in ascending order. Then, we iterate through the sorted players array using a pointer i. For each player, we iterate through the sorted trainers array using a pointer j, starting from where we left off in the previous iteration. We find the first trainer whose capacity is greater than or equal to the current player's ability. If we find a match, we increment both i and j and continue. If we reach the end of the trainers array without finding a match for the current player, it means no more matches are possible, and we return the current number of matches found so far. If we successfully iterate through all players, it means all players found a match, and we return the total number of players.

Time and Space Complexity

• Time Complexity: O(m log m + n log n), where m is the length of players and n is the length of trainers. This is dominated by the sorting of the two arrays. The two-pointer iteration is linear in the smaller of m and n.
• Space Complexity: O(log m + log n) or O(1) depending on the sorting implementation. In-place sorting algorithms would result in O(1) space complexity.

Code Implementation

Here's the code implementation in several programming languages:

Python:

def matchPlayersAndTrainers(players, trainers):
    players.sort()
    trainers.sort()
    i, j = 0, 0
    count = 0
    while i < len(players) and j < len(trainers):
        if players[i] <= trainers[j]:
            count += 1
            i += 1
            j += 1
        else:
            j += 1
    return count
 

Java:

import java.util.Arrays;
 
class Solution {
    public int matchPlayersAndTrainers(int[] players, int[] trainers) {
        Arrays.sort(players);
        Arrays.sort(trainers);
        int i = 0, j = 0, count = 0;
        while (i < players.length && j < trainers.length) {
            if (players[i] <= trainers[j]) {
                count++;
                i++;
                j++;
            } else {
                j++;
            }
        }
        return count;
    }
}

C++:

#include <algorithm>
#include <vector>
 
class Solution {
public:
    int matchPlayersAndTrainers(std::vector<int>& players, std::vector<int>& trainers) {
        std::sort(players.begin(), players.end());
        std::sort(trainers.begin(), trainers.end());
        int i = 0, j = 0, count = 0;
        while (i < players.size() && j < trainers.size()) {
            if (players[i] <= trainers[j]) {
                count++;
                i++;
                j++;
            } else {
                j++;
            }
        }
        return count;
    }
};

JavaScript:

/**
 * @param {number[]} players
 * @param {number[]} trainers
 * @return {number}
 */
var matchPlayersAndTrainers = function(players, trainers) {
    players.sort((a, b) => a - b);
    trainers.sort((a, b) => a - b);
    let i = 0, j = 0, count = 0;
    while (i < players.length && j < trainers.length) {
        if (players[i] <= trainers[j]) {
            count++;
            i++;
            j++;
        } else {
            j++;
        }
    }
    return count;
};

These code snippets all implement the same greedy two-pointer algorithm, demonstrating its efficiency and adaptability across different programming languages. Remember that the efficiency hinges on the efficient sorting algorithms used by each language's sort() function.