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

来源第 87 场双周赛 Q2难度中等分数1381

题目描述

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

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

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

示例 1：

输入：players = [4,7,9], trainers = [8,2,5,8]
输出：2
解释：
得到两个匹配的一种方案是：
- players[0] 与 trainers[0] 匹配，因为 4 <= 8 。
- players[1] 与 trainers[3] 匹配，因为 7 <= 8 。
可以证明 2 是可以形成的最大匹配数。

示例 2：

输入：players = [1,1,1], trainers = [10]
输出：1
解释：
训练师可以匹配所有 3 个运动员
每个运动员至多只能匹配一个训练师，所以最大答案是 1 。

提示：

1 <= players.length, trainers.length <= 10⁵
1 <= players[i], trainers[j] <= 10⁹

解法

方法一：贪心 + 双指针

思考

\(n,m \le 10^5\)，两两尝试配对会超时。训练师若能匹配更弱的运动员，也就能匹配更强的运动员，所以应把刚好够用的训练师分给当前最弱的运动员。

两边按能力升序排列后，从弱到强处理运动员，训练师指针只向前走：能力不足的跳过，遇到第一个够用的就配上一对。总时间由排序决定。

把运动员和训练师都按能力从小到大排序。指针 \(i\) 和 \(j\) 分别指向当前考虑到的运动员和训练师。

从最弱的运动员开始匹配。训练师能力低于这名运动员时，将 \(j\) 右移，直到能力足够，或训练师已经用完。训练师用完后，后面的运动员只会更强，匹配结束，答案就是已经配上的人数 \(i\)。否则当前这一对可以匹配，两个指针各前进一步。所有运动员都匹配成功时，返回运动员人数。

时间复杂度 \(O(m \times \log m + n \times \log n)\)，空间复杂度 \(O(\max(\log m, \log n))\)。其中 \(m\) 和 \(n\) 分别为运动员和训练师的数量。

Python3JavaC++GoTypeScriptRust

class Solution:
    def matchPlayersAndTrainers(self, players: List[int], trainers: List[int]) -> int:
        players.sort()
        trainers.sort()
        j, n = 0, len(trainers)
        for i, p in enumerate(players):
            while j < n and trainers[j] < p:
                j += 1
            if j == n:
                return i
            j += 1
        return len(players)

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

class Solution {
public:
    int matchPlayersAndTrainers(vector<int>& players, vector<int>& trainers) {
        ranges::sort(players);
        ranges::sort(trainers);
        int m = players.size(), n = trainers.size();
        for (int i = 0, j = 0; i < m; ++i, ++j) {
            while (j < n && trainers[j] < players[i]) {
                ++j;
            }
            if (j == n) {
                return i;
            }
        }
        return m;
    }
};

func matchPlayersAndTrainers(players []int, trainers []int) int {
    sort.Ints(players)
    sort.Ints(trainers)
    m, n := len(players), len(trainers)
    for i, j := 0, 0; i < m; i, j = i+1, j+1 {
        for j < n && trainers[j] < players[i] {
            j++
        }
        if j == n {
            return i
        }
    }
    return m
}

function matchPlayersAndTrainers(players: number[], trainers: number[]): number {
    players.sort((a, b) => a - b);
    trainers.sort((a, b) => a - b);
    const [m, n] = [players.length, trainers.length];
    for (let i = 0, j = 0; i < m; ++i, ++j) {
        while (j < n && trainers[j] < players[i]) {
            ++j;
        }
        if (j === n) {
            return i;
        }
    }
    return m;
}

impl Solution {
    pub fn match_players_and_trainers(mut players: Vec<i32>, mut trainers: Vec<i32>) -> i32 {
        players.sort();
        trainers.sort();
        let mut j = 0;
        let n = trainers.len();
        for (i, &p) in players.iter().enumerate() {
            while j < n && trainers[j] < p {
                j += 1;
            }
            if j == n {
                return i as i32;
            }
            j += 1;
        }
        players.len() as i32
    }
}

方法二：贪心 + 双指针（遍历训练师）

思考

方法一在处理每名运动员时，还要用内层循环跳过能力不足的训练师，训练师用完则提前返回。改成遍历训练师之后，这两步都可以省去。

两边按能力升序排列，从弱到强查看训练师，指针停在最弱的未匹配运动员上。训练师能力不足时，剩余运动员只会更强，直接跳过。能力足够就完成匹配，指针前进一步。指针最终的位置就是匹配数，复杂度与方法一相同。

同样先把运动员和训练师按能力从小到大排序。指针 \(j\) 指向尚未匹配的最弱运动员，初始为 \(0\)。

从弱到强查看每名训练师。若仍有运动员未匹配，且该运动员的能力不超过这名训练师，就配成一对，并将 \(j\) 加一。否则这名训练师无法匹配剩下的任何运动员，直接跳过。遍历结束后，\(j\) 就是最大匹配数。