2410. Maximum Matching of Players With Trainers

[mah-shamim]

Topics: Array, Two Pointers, Greedy, Sorting

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.

Hint:

1. Sort both the arrays.
2. Construct the matching greedily.

[mah-shamim]

We need to find the maximum number of matchings between players and trainers such that each player's ability is less than or equal to the trainer's capacity. Each player can match with at most one trainer, and each trainer can match with at most one player.

Approach

1. Sorting: The first step involves sorting both the players and trainers arrays in ascending order. Sorting helps in efficiently applying a greedy strategy to find the maximum matchings.
2. Greedy Matching with Two Pointers: Using two pointers, one for each array, we traverse through both arrays. For each player, starting from the smallest, we find the smallest available trainer that can accommodate the player's ability. If such a trainer is found, we count this as a match and move both pointers forward. If not, we move the trainer pointer forward to check the next larger trainer. This ensures that we use the smallest suitable trainer for each player, leaving larger trainers for potentially larger players, thus maximizing the number of matchings.

Let's implement this solution in PHP: 2410. Maximum Matching of Players With Trainers

<?php
/**
 * @param Integer[] $players
 * @param Integer[] $trainers
 * @return Integer
 */
function matchPlayersAndTrainers($players, $trainers) {
    sort($players);
    sort($trainers);
    $count = 0;
    $i = 0;
    $j = 0;
    $n = count($players);
    $m = count($trainers);
    
    while ($i < $n && $j < $m) {
        if ($players[$i] <= $trainers[$j]) {
            $count++;
            $i++;
            $j++;
        } else {
            $j++;
        }
    }
    
    return $count;
}

// Test cases
// Example 1
$players = array(4, 7, 9);
$trainers = array(8, 2, 5, 8);
echo matchPlayersAndTrainers($players, $trainers); // Output: 2

echo "\n";

// Example 2
$players = array(1, 1, 1);
$trainers = array(10);
echo matchPlayersAndTrainers($players, $trainers); // Output: 1
?>

Explanation:

1. Sorting Arrays: Both the players and trainers arrays are sorted in ascending order. This allows us to systematically check each player against the trainers starting from the smallest values.
2. Two Pointers Technique:
   • The pointer $i starts at the beginning of the sorted players array.
   • The pointer $j starts at the beginning of the sorted trainers array.
   • For each player, we check if the current trainer's capacity is sufficient (i.e., $players[$i] <= $trainers[$j]). If yes, we increment the match count and move both pointers forward. If not, we only move the trainer pointer forward to check the next trainer.
3. Termination: The loop continues until either all players are processed or all trainers are exhausted. The result is the total count of successful matchings, which is returned as the solution.

This approach efficiently maximizes the number of matchings by leveraging sorting and a greedy strategy, ensuring optimal performance with a time complexity dominated by the sorting steps: O(n log n + m log m), where n and m are the lengths of the players and trainers arrays, respectively. The subsequent two-pointer traversal operates in O(n + m) time.

[kovatz]

Thanks for solving the problem of "Maximum Matching of Players With Trainers"

[mah-shamim]

Thanks