2410. Maximum Matching of Players With Trainers
Description
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.
Solutions
Solution 1: Greedy + Two Pointers
According to the problem description, each athlete should be matched with the trainer whose ability value is as close as possible. Therefore, we can sort the ability values of both athletes and trainers, and then use the two-pointer method for matching.
We use two pointers $i$ and $j$ to point to the arrays of athletes and trainers, respectively, both initially pointing to the start of the arrays. Then we traverse the ability values of the athletes one by one. If the current trainer's ability value is less than the current athlete's ability value, we move the trainer's pointer to the right by one position until we find a trainer whose ability value is greater than or equal to the current athlete's. If no such trainer is found, it means the current athlete cannot be matched with any trainer, and we return the current athlete's index. Otherwise, we can match the current athlete with the trainer, and then move both pointers to the right by one position. Continue this process until all athletes have been traversed.
If we traverse all athletes, it means all athletes can be matched with trainers, and we return the number of athletes.
The time complexity is $O(m \times \log m + n \times \log n)$, and the space complexity is $O(\max(\log m, \log n))$. Here, $m$ and $n$ are the numbers of athletes and trainers, respectively.
1 2 3 4 5 6 7 8 9 10 11 12 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|