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

运动员和训练师，最多能凑成几对搭档

给一排运动员的能力 players 和一排训练师的能力 trainers。运动员能力小于等于训练师能力就能配成一对；一名运动员至多配一位训练师，一位训练师至多带一名运动员。求最多配成几对。题面 players=[4,7,9]、trainers=[8,2,5,8] 答案是 2：能力 4、7 各配一个 8，最强的 9 谁都够不上，落空。

给每名运动员挨个翻训练师，卡在哪

对每名运动员从头翻还没占用的训练师、挑个够得上的配上，m 名运动员每人最坏翻 n 位，时间 O(m·n)，两边上千位就跑不动。更麻烦的是「配哪一位」没准谱：一名运动员常有好几位训练师够格，随手挑，可能占掉本该留给别人的搭档，总对数反而少。

为什么让最弱的运动员先挑，反而配得最多

把两个数组都从小到大排好，一条朴素又正确的规则就浮出来：让当前最弱的运动员，配够得上他的、能力最弱的那位训练师。这套「每步都挑当下最省」的贪心在这儿成立：强训练师留着还能压更强的运动员，弱运动员门槛最低，拿刚够格的打发他最不浪费。

为什么最优？把最优解一步步换成贪心、看对数会不会掉，就说清了：假设某最优解里最弱运动员没配那位刚够格的最弱训练师 t，t 要么闲着、要么被更强的运动员 q 占着。t 闲着就把弱运动员挪到 t 上多配一对；t 被 q 占，就让两人对换，弱运动员拿走本就够格的 t，q 顶到弱运动员原先那位更强训练师、照样压得住。对数没少却成了贪心，可见贪心不比最优差。

两个指针怎么走，才不用回头重扫

排好序后两个指针一齐往右挪。i 指当前要配的运动员（从最弱起），j 指当前考察的训练师。只要 trainers[j] ＜ players[i]，这训练师太弱、对更强的运动员更没用，j 往右跳过；一旦 trainers[j] ≥ players[i]，配成一对，i、j 同时前进。若 j 走到队尾还没配上，剩下的运动员更强、都没搭档，对数就此定下。i、j 各只走一趟不回头，扫描是线性的。

题面 [4,7,9] 配 [8,2,5,8]，指针怎么挪

排完序 players=[4,7,9]、trainers=[2,5,8,8]，j 从 0 起。运动员 4：j 指训练师 2，2＜4 托不起，j 挪到 1；训练师 5≥4 够格，配成第 1 对，i、j 各进一格，j 到 2。运动员 7：j 指训练师 8，8≥7，配成第 2 对，j 进到 3。运动员 9：j 指训练师 8，8＜9 太弱，j 挪到 4 越过队尾，训练师用光，这名运动员配不上，收工。配成 2 对就是最大匹配数。

排序省不掉，配成一对后 j 一步都不能赖着

开销压在两次排序上，时间 O(m log m + n log n)；双指针只线性扫一遍，被排序盖过。空间除排序内部的栈外只几个指针，O(1)。最容易栽的是省掉排序直接上双指针：贪心全靠「从小到大」撑着，两队不排好，「最弱配够得上的最弱」就无从谈起，答案随手就偏。配成一对后 j 赖着不动是另一处坑：一位训练师只带一人，配上就用掉了，j 不前进会把同一位重复算进好几对。还有判断够格要用小于等于：相等也能配，写成严格小于会漏掉打平的两人。

Python

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)

C++

#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;
    }
};

Java

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;
    }
}