运动员和训练师的最大匹配数 图解题解

这道题到底在问什么

输入

players=[4,7,9], trainers=[8,2,5,8]

输出

2

输入

players=[1,1,1], trainers=[10]

输出

1

最优解：一步一步想明白

1. 3记牢这一句:排完序后,让最弱的运动员去配够得上他的最弱训练师。这样强的训练师就被省下来留给强运动员,谁都不浪费,配出来的对数就是最多的。下面从最弱的运动员开始,一位一位配。
2. 4先看没排序的原始数据。上面横排是训练师的能力 7、2、9、3、11、7、4,侧栏是运动员的能力 8、5、13、6、10。这样乱着放没法贪心,贪心的前提是两边都得从小到大排好队,这样才能让最弱的先配最弱的。
3. 5两边各自排好序。训练师从小到大是 2、3、4、7、7、9、11,运动员从小到大是 5、6、8、10、13。现在准备工作做完了,让指针 j 从最左边的训练师开始,依次给每位运动员找搭档。
4. 6规则再明确一下:侧栏最上面高亮的是当前轮到的运动员,永远从最弱的那位开始;主舞台上高亮的是指针 j 当前指着的训练师。给这位运动员找搭档时,j 只会往右走,不回头。够格就染绿配对,太弱就染灰跳过。开始。
5. 7轮到能力 5 的运动员。指针 j 没有回头,接着从上一位停下的地方往右看,现在指着能力 2 的训练师。看看这位训练师托不托得起 5。
6. 8训练师能力 2 比运动员 5 还小,带不动他,配不了。而且后面的运动员只会更强,这位训练师对谁都没用了,直接染灰划掉,指针 j 往右挪一格。
7. 9指针 j 落到能力 3 的训练师上,继续拿它和运动员 5 比,看这次够不够格。
8. 10训练师能力 3 比运动员 5 还小,带不动他,配不了。而且后面的运动员只会更强,这位训练师对谁都没用了,直接染灰划掉,指针 j 往右挪一格。
9. 11指针 j 落到能力 4 的训练师上,继续拿它和运动员 5 比,看这次够不够格。
10. 12训练师能力 4 比运动员 5 还小,带不动他,配不了。而且后面的运动员只会更强,这位训练师对谁都没用了,直接染灰划掉,指针 j 往右挪一格。
11. 13指针 j 落到能力 7 的训练师上,继续拿它和运动员 5 比,看这次够不够格。
12. 14训练师能力 7 大于等于运动员 5,托得起!这一对成了,把这位训练师染绿。运动员 5 也算配上了。已匹配数加到 1。接着两个指针一起往后挪,服务下一位更强的运动员。
13. 15轮到能力 6 的运动员。指针 j 没有回头,接着从上一位停下的地方往右看,现在指着能力 7 的训练师。看看这位训练师托不托得起 6。
14. 16训练师能力 7 大于等于运动员 6,托得起!这一对成了,把这位训练师染绿。运动员 6 也算配上了。已匹配数加到 2。接着两个指针一起往后挪,服务下一位更强的运动员。
15. 17轮到能力 8 的运动员。指针 j 没有回头,接着从上一位停下的地方往右看,现在指着能力 9 的训练师。看看这位训练师托不托得起 8。
16. 18训练师能力 9 大于等于运动员 8,托得起!这一对成了,把这位训练师染绿。运动员 8 也算配上了。已匹配数加到 3。接着两个指针一起往后挪,服务下一位更强的运动员。
17. 19轮到能力 10 的运动员。指针 j 没有回头,接着从上一位停下的地方往右看,现在指着能力 11 的训练师。看看这位训练师托不托得起 10。
18. 20训练师能力 11 大于等于运动员 10,托得起!这一对成了,把这位训练师染绿。运动员 10 也算配上了。已匹配数加到 4。接着两个指针一起往后挪,服务下一位更强的运动员。
19. 21轮到能力 13 的运动员,可指针 j 已经扫到训练师队伍的尽头,一个能用的训练师都不剩了。这位运动员再强也没人带,只能落空。
20. 22既然连最弱的运动员之后的强手都配光了训练师,后面比他更强的运动员更不可能有搭档,直接收工。此刻已经配好的对数就是答案 4。
21. 23回看全程。运动员 5、6、8、10 各自配到了一位刚好够得上的训练师,四位训练师染成绿色;被跳过的弱训练师染灰。最强的运动员 13 到最后没有训练师托得起,落空了。数一数绿色的对子,一共 4 对,这就是最大匹配数。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
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)

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    int matchPlayersAndTrainers(vector<int>& players, vector<int>& trainers) {
        sort(players.begin(), players.end());
        sort(trainers.begin(), trainers.end());
        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;
    }
};

import java.util.*;
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;
    }
}

复杂度

面试官可能追问