2410. Maximum Matching of Players With Trainers

Difficulty: Medium

Topics:Array,Two Pointers,Greedy,Sorting

You are given a0-indexed integer arrayplayers, whereplayers[i] represents theability of theith player. You are also given a0-indexed integer arraytrainers, wheretrainers[j] represents thetraining capacity of thejth trainer.

Theith player canmatch with thejth trainer if the player's ability isless than or equal to the trainer's training capacity. Additionally, theith player can be matched with at most one trainer, and thejth trainer can be matched with at most one player.

Returnthemaximum number of matchings betweenplayers andtrainers 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 as445: Assign Cookies.

Hint:

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

Solution:

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 theplayers andtrainers 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 */functionmatchPlayersAndTrainers($players,$trainers){........./**     * go to ./solution.php     */}// Test cases// Example 1$players=array(4,7,9);$trainers=array(8,2,5,8);echomatchPlayersAndTrainers($players,$trainers);// Output: 2echo"\n";// Example 2$players=array(1,1,1);$trainers=array(10);echomatchPlayersAndTrainers($players,$trainers);// Output: 1?>

Explanation:

1. Sorting Arrays: Both theplayers andtrainers 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 sortedplayers array.
   • The pointer$j starts at the beginning of the sortedtrainers 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), wheren andm are the lengths of theplayers andtrainers arrays, respectively. The subsequent two-pointer traversal operates inO(n + m) time.

Contact Links

If you found this series helpful, please consider giving therepository a star on GitHub or sharing the post on your favorite social networks 😍.Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

• LinkedIn
• GitHub