[LeetCode] 2410. Maximum Matching of Players With Trainers

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.

运动员和训练师的最大匹配数。

给你一个下标从 0 开始的整数数组 players ，其中 players[i] 表示第 i 名运动员的 能力 值，同时给你一个下标从 0 开始的整数数组 trainers ，其中 trainers[j] 表示第 j 名训练师的 训练能力值 。

如果第 i 名运动员的能力值 小于等于 第 j 名训练师的能力值，那么第 i 名运动员可以 匹配 第 j 名训练师。除此以外，每名运动员至多可以匹配一位训练师，每位训练师最多可以匹配一位运动员。

请你返回满足上述要求 players 和 trainers 的 最大 匹配数。

思路

思路是排序 + 双指针。对 players 和 trainers 都进行排序，然后用两个指针分别指向 players 和 trainers 的开头。遍历 players，如果当前 player 能够匹配当前 trainer，就将匹配数加一，并将两个指针都向后移动；如果不能匹配，就只移动 trainer 的指针，直到找到一个可以匹配的 trainer 或者遍历完所有的 trainers。

复杂度

时间O(nlogn)
空间O(1)

代码

Java实现

class Solution {
    public int matchPlayersAndTrainers(int[] players, int[] trainers) {
        Arrays.sort(players);
        Arrays.sort(trainers);
        int m = players.length;
        int n = trainers.length;
        int i = 0;
        int j = 0;
        while (i < m && j < n) {
            if (players[i] <= trainers[j]) {
                i++;
            }
            j++;
        }
        return i;
    }
}