2410. Maximum Matching of Players With Trainers


Problem Description

In this LeetCode problem, you are given two 0-indexed integer arrays: players and trainers. Each entry in the players array represents the ability of a particular player, and each entry in the trainers array represents the training capacity of a particular trainer. A player can be matched with a trainer if the player's ability is less than or equal to the trainer's capacity. It's important to note that each player can only be matched with one trainer, and each trainer can match with only one player. The task is to find the maximum number of such player-trainer pairings where the conditions of matching ability to capacity are met.

Intuition

The intuition behind the solution is straightforward: we want to pair as many players with trainers as we can, prioritizing the pairing of less able players with trainers who have just enough capacity to train them. This ensures that we do not 'waste' a trainer with high capacity on a player with low ability when that trainer could be matched with a more able player instead.

To achieve this, we sort both the players and trainers arrays. Sorting helps us easily compare the least able player with the least capable trainer and move up their respective arrays. If a match is found, both the player and the trainer are effectively removed from the potential pool by moving to the next elements in the arrays (incrementing the index). If no match is found, we move up the trainers array to find the next trainer with a higher capacity that might match the player’s ability.

The result is incrementally built by adding a match whenever we find a capable trainer for a player. We stop when we've either paired all players or run out of trainers. The sum of matches made gives us the maximum number of possible pairings.

Learn more about Greedy, Two Pointers and Sorting patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece:

Which algorithm should you use to find a node that is close to the root of the tree?

Solution Approach

The implementation provided uses a simple but effective greedy approach, heavily relying on sorting. The steps involve:

  1. Sorting the players array in ascending order, which ensures we start with the player with the lowest ability.

  2. Sorting the trainers array in ascending order, which allows us to start with the trainer having the lowest capacity.

The algorithm works with two pointers, one (i) iterating through the players array, and the other (j) through the trainers array.

Here is the implementation broken down:

  • Initialize a variable ans to 0 to keep track of the number of matches made.

  • Initialize the trainer index pointer j to 0.

  • Iterate over each player p in the sorted players list using a for-loop.

    • Within the loop, proceed with an inner while-loop which continues as long as j is less than the length of trainers and the current trainer's capacity trainers[j] is less than the ability of the player p. The purpose of this loop is to find the first trainer in the sorted list whose capacity is sufficient to train the player.

    • After the while-loop, if j is still within the bounds of the trainers array, it means a suitable trainer has been found for the player p. We increment ans to count the match and also increment j to move to the next trainer.

  • Once all players have been considered, return the value of ans.

Algorithm and Data Structures:

  • Lists: The main data structure used here are lists (players and trainers), which are sorted.

  • Greedy approach: The algorithm uses a greedy method by matching each player with the "smallest" available trainer that can train them.

  • Two pointers: It uses two pointers to pair players with trainers without revisiting or re-comparing them, thus optimizing the process.

  • Sorting: By sorting the arrays, the solution leverages the property that once a player cannot be paired with a current trainer, they cannot be paired with any trainers before that one in the sorted list either.

Patterns used:

  • Sorting and Two-pointers: This is a common pattern for efficiently pairing elements from two different sorted lists.
Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

How many ways can you arrange the three letters A, B and C?

Example Walkthrough

Let's say we have the following players and trainers arrays:

  • players: [2, 3, 4]
  • trainers: [1, 2, 5]

Following the solution approach:

  1. We first sort both the players and trainers arrays:

    After sorting,

    • players: [2, 3, 4] (already sorted)
    • trainers: [1, 2, 5] (already sorted)
  2. We initialize ans to 0. This variable will keep track of the successful player-trainer matches.

  3. We also initialize the trainer index pointer j to 0.

Now, let's go through each player and try to find a trainer match:

  • Player with ability 2 is the first in the players array.

    • We check the trainers in order: trainer 1 cannot train the player because the trainer's capacity is too low.
    • Move to the next trainer (2), and we find a match. Trainer 2 can train the player with ability 2.
    • We increment ans to 1 and move to the next trainer (j becomes 2).
  • Player with ability 3 is the next.

    • The trainer in position 2 in the sorted trainers list has a capacity of 5, which is sufficient.
    • We match this player with the trainer.
    • We increment ans to 2, and since there are no more trainers, we move on to the final player.
  • Player with ability 4:

    • There are no more trainers to compare since we exceeded the length of the trainers array.

At the end of this process, the value of ans is 2, which signifies that we were able to match two pairs of players and trainers successfully.

Solution Implementation

1from typing import List  # Import List from typing module for type hints
2
3class Solution:
4    def matchPlayersAndTrainers(self, players: List[int], trainers: List[int]) -> int:
5        # Sort the list of players in ascending order
6        players.sort()
7        # Sort the list of trainers in ascending order
8        trainers.sort()
9      
10        # Initialize the count of matched players and trainers
11        match_count = 0
12        # Initialize the pointer for trainers list
13        trainer_index = 0
14      
15        # Iterate over each player in the sorted list
16        for player in players:
17            # Skip trainers which have less capacity than the current player's strength
18            while trainer_index < len(trainers) and trainers[trainer_index] < player:
19                trainer_index += 1
20              
21            # If there is a trainer that can match the current player
22            if trainer_index < len(trainers):
23                # Increment the match count
24                match_count += 1
25                # Move to the next trainer for the next player
26                trainer_index += 1
27      
28        # Return the total number of matches
29        return match_count
30
1class Solution {
2    public int matchPlayersAndTrainers(int[] players, int[] trainers) {
3        // Sort the players array in ascending order
4        Arrays.sort(players);
5        // Sort the trainers array in ascending order
6        Arrays.sort(trainers);
7
8        // Initialize the count of matches to 0
9        int matches = 0;
10        // Initialize the index for trainers to 0
11        int trainerIndex = 0;
12
13        // Iterate over each player
14        for (int player : players) {
15            // Increment the trainerIndex until we find a trainer that can match the player
16            while (trainerIndex < trainers.length && trainers[trainerIndex] < player) {
17                trainerIndex++;
18            }
19            // If there is a trainer that can match the player, increment the match count
20            if (trainerIndex < trainers.length) {
21                matches++; // A match is found
22                trainerIndex++; // Move to the next trainer.
23            }
24        }
25        // Return the total count of matches
26        return matches;
27    }
28}
29
1#include <vector>
2#include <algorithm> // Include the necessary header for std::sort
3
4class Solution {
5public:
6    // Function to match players with trainers based on their strength.
7    // Each player can only be matched with a trainer that is equal or greater in strength.
8    int matchPlayersAndTrainers(vector<int>& players, vector<int>& trainers) {
9        std::sort(players.begin(), players.end()); // Sort the players in ascending order
10        std::sort(trainers.begin(), trainers.end()); // Sort the trainers in ascending order
11
12        int matches = 0; // Initialize the number of matches to zero
13        int trainersIndex = 0; // Initialize the trainers index to the start of the array
14
15        // Iterate through each player
16        for (int playerStrength : players) {
17            // Find a trainer that can match the current player's strength
18            while (trainersIndex < trainers.size() && trainers[trainersIndex] < playerStrength) {
19                trainersIndex++; // Increment trainers index if the current trainer is weaker than the player
20            }
21
22            // If a suitable trainer is found, make the match
23            if (trainersIndex < trainers.size()) {
24                matches++; // Increment match count
25                trainersIndex++; // Move to the next trainer for the following players
26            }
27        }
28
29        return matches; // Return the total number of matches made
30    }
31};
32
1// Import the necessary module for sorting
2import { sort } from 'some-sorting-module'; // Please replace 'some-sorting-module' with the actual module you would use for sorting
3
4// Function to sort an array in ascending order
5function sortArrayAscending(array: number[]): number[] {
6    return sort(array, (a, b) => a - b);
7}
8
9// Function to match players with trainers based on their strength.
10// Each player can only be matched with a trainer that is equal or greater in strength.
11function matchPlayersAndTrainers(players: number[], trainers: number[]): number {
12    // Sort the players and trainers in ascending order
13    const sortedPlayers: number[] = sortArrayAscending(players);
14    const sortedTrainers: number[] = sortArrayAscending(trainers);
15
16    let matches: number = 0; // Initialize the number of matches to zero
17    let trainersIndex: number = 0; // Initialize the trainers index to the start of the array
18
19    // Iterate through each player and match with trainers based on strength
20    for (const playerStrength of sortedPlayers) {
21        // Find a trainer that can match the current player's strength
22        while (trainersIndex < sortedTrainers.length && sortedTrainers[trainersIndex] < playerStrength) {
23            trainersIndex++; // Increment trainers index if the current trainer is weaker than the player
24        }
25
26        // If a suitable trainer is found, make the match
27        if (trainersIndex < sortedTrainers.length) {
28            matches++; // Increment match count
29            trainersIndex++; // Move to the next trainer for the following players
30        }
31    }
32
33    return matches; // Return the total number of matches made
34}
35
36// Export the function if this is part of a module
37export { matchPlayersAndTrainers };
38
Not Sure What to Study? Take the 2-min Quiz:

What is the best way of checking if an element exists in a sorted array once in terms of time complexity? Select the best that applies.

Time and Space Complexity

Time Complexity

The time complexity of the code is determined by the sorting operations and the subsequent for-loop with the inner while loop.

  1. Sorting both the players and trainers list takes O(nlogn) and O(mlogm), respectively, where n is the number of players and m is the number of trainers.

  2. The for-loop iterates over each player, which is O(n). Within this loop, the while loop progresses without resetting, which makes it linear over m elements of trainers in total. In the worst case, all players are checked against all trainers, hence it contributes a maximum of O(m) time complexity.

The combined time complexity of these operations would be O(nlogn) + O(mlogm) + O(n + m). However, since O(nlogn) and O(mlogm) are the dominant terms, the overall time complexity simplifies to O(nlogn + mlogm).

Space Complexity

The space complexity of the code is O(1), which is the additional space required. The sorting happens in place, and no additional data structures are used aside from a few variables for keeping track of indexes and the answer.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following problems can be solved with backtracking (select multiple)


Recommended Readings


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫