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 <= 1051 <= players[i], trainers[j] <= 109
Note: This question is the same as 445: Assign Cookies.
This approach involves sorting both the players and trainers arrays. Then, using a two-pointer method, we try to find the maximum number of pairings possible. We move pointers on players and trainers based on the comparison between the player's ability and the trainer's capacity.
The solution starts by sorting both arrays, players and trainers. Then, it utilizes two pointers, one for each array. If the current player's ability is less than or equal to the current trainer's capacity, a match is counted, and both pointers advance. If not, only the trainer's pointer advances to find a suitable trainer.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n log n + m log m), where n and m are the lengths of the players and trainers arrays respectively, due to sorting.
Space Complexity: O(1), as no additional space proportional to input size is used.
This approach is based on using a greedy algorithm with the help of sets or heaps to facilitate a similar matching process. By leveraging the properties of sets, we can efficiently manage player-trainer pairings as we iterate through sorted lists.
In this C++ solution, we use a multiset to store trainers. We sort players and use the lower_bound function to find the minimum capacity trainer for each player efficiently. Once a match is found, the trainer is removed from the set.
Python
Time Complexity: O(n log n + m log m) for sorting and finding matches.
Space Complexity: O(m) for storing trainers.
| Approach | Complexity |
|---|---|
| Two-Pointer Technique after Sorting | Time Complexity: O(n log n + m log m), where n and m are the lengths of the |
| Greedy Matching with Sets | Time Complexity: O(n log n + m log m) for sorting and finding matches. |
The unfair way I got good at Leetcode • Dave Burji • 596,394 views views
Watch 9 more video solutions →Practice Maximum Matching of Players With Trainers with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor