题目描述
思路解析
一句话答案：LeetCode 2410 运动员和训练师的最大匹配数：两个能力数组各自排序后双指针贪心，让最弱运动员配够得上他的最弱训练师，配上就双双前进。时间 O(m log m + n log n)、空间 O(1)。
运动员和训练师，最多能凑成几对搭档
给一排运动员的能力 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 不前进会把同一位重复算进好几对。还有判断够格要用小于等于：相等也能配，写成严格小于会漏掉打平的两人。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记牢这一句:排完序后,让最弱的运动员去配够得上他的最弱训练师。这样强的训练师就被省下来留给强运动员,谁都不浪费,配出来的对数就是最多的。下面从最弱的运动员开始,一位一位配。
排序前 · 原始输入：先看没排序的原始数据。上面横排是训练师的能力 7、2、9、3、11、7、4,侧栏是运动员的能力 8、5、13、6、10。这样乱着放没法贪心,贪心的前提是两边都得从小到大排好队,这样才能让最弱的先配最弱的。
排序后 · 两队都从小到大：两边各自排好序。训练师从小到大是 2、3、4、7、7、9、11,运动员从小到大是 5、6、8、10、13。现在准备工作做完了,让指针 j 从最左边的训练师开始,依次给每位运动员找搭档。
开工规则 · 弱运动员配够得上的最弱训练师：规则再明确一下:侧栏最上面高亮的是当前轮到的运动员,永远从最弱的那位开始;主舞台上高亮的是指针 j 当前指着的训练师。给这位运动员找搭档时,j 只会往右走,不回头。够格就染绿配对,太弱就染灰跳过。开始。
轮到运动员 5 · 从训练师 2 开始看：轮到能力 5 的运动员。指针 j 没有回头,接着从上一位停下的地方往右看,现在指着能力 2 的训练师。看看这位训练师托不托得起 5。
训练师 2 撑不起 5 · 染灰跳过：训练师能力 2 比运动员 5 还小,带不动他,配不了。而且后面的运动员只会更强,这位训练师对谁都没用了,直接染灰划掉,指针 j 往右挪一格。
看下一位训练师 3：指针 j 落到能力 3 的训练师上,继续拿它和运动员 5 比,看这次够不够格。
训练师 3 撑不起 5 · 染灰跳过：训练师能力 3 比运动员 5 还小,带不动他,配不了。而且后面的运动员只会更强,这位训练师对谁都没用了,直接染灰划掉,指针 j 往右挪一格。
看下一位训练师 4：指针 j 落到能力 4 的训练师上,继续拿它和运动员 5 比,看这次够不够格。
训练师 4 撑不起 5 · 染灰跳过：训练师能力 4 比运动员 5 还小,带不动他,配不了。而且后面的运动员只会更强,这位训练师对谁都没用了,直接染灰划掉,指针 j 往右挪一格。
看下一位训练师 7：指针 j 落到能力 7 的训练师上,继续拿它和运动员 5 比,看这次够不够格。
运动员 5 配训练师 7 · 成对!：训练师能力 7 大于等于运动员 5,托得起!这一对成了,把这位训练师染绿。运动员 5 也算配上了。已匹配数加到 1。接着两个指针一起往后挪,服务下一位更强的运动员。
轮到运动员 6 · 从训练师 7 开始看：轮到能力 6 的运动员。指针 j 没有回头,接着从上一位停下的地方往右看,现在指着能力 7 的训练师。看看这位训练师托不托得起 6。
运动员 6 配训练师 7 · 成对!：训练师能力 7 大于等于运动员 6,托得起!这一对成了,把这位训练师染绿。运动员 6 也算配上了。已匹配数加到 2。接着两个指针一起往后挪,服务下一位更强的运动员。
轮到运动员 8 · 从训练师 9 开始看：轮到能力 8 的运动员。指针 j 没有回头,接着从上一位停下的地方往右看,现在指着能力 9 的训练师。看看这位训练师托不托得起 8。
运动员 8 配训练师 9 · 成对!：训练师能力 9 大于等于运动员 8,托得起!这一对成了,把这位训练师染绿。运动员 8 也算配上了。已匹配数加到 3。接着两个指针一起往后挪,服务下一位更强的运动员。
轮到运动员 10 · 从训练师 11 开始看：轮到能力 10 的运动员。指针 j 没有回头,接着从上一位停下的地方往右看,现在指着能力 11 的训练师。看看这位训练师托不托得起 10。
运动员 10 配训练师 11 · 成对!：训练师能力 11 大于等于运动员 10,托得起!这一对成了,把这位训练师染绿。运动员 10 也算配上了。已匹配数加到 4。接着两个指针一起往后挪,服务下一位更强的运动员。
轮到运动员 13 · 训练师已用光：轮到能力 13 的运动员,可指针 j 已经扫到训练师队伍的尽头,一个能用的训练师都不剩了。这位运动员再强也没人带,只能落空。
运动员 13 落空 · 结束：既然连最弱的运动员之后的强手都配光了训练师,后面比他更强的运动员更不可能有搭档,直接收工。此刻已经配好的对数就是答案 4。
回放 · 四对配成,答案 4：回看全程。运动员 5、6、8、10 各自配到了一位刚好够得上的训练师,四位训练师染成绿色;被跳过的弱训练师染灰。最强的运动员 13 到最后没有训练师托得起,落空了。数一数绿色的对子,一共 4 对,这就是最大匹配数。
边界想清:训练师少则对数被训练师数卡住、谁都够不上则 0 对、能力相等仍可配成一对。
面试重点:排序加双指针贪心、交换论证证明最优、复杂度由两次排序主导。
参考代码
from __future__ import annotationsfrom 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)复杂度
- 时间：O(m log m + n log n)，m 名运动员、n 位训练师。主要开销是两次排序,分别是 m log m 和 n log n;后面的双指针扫描里 i 和 j 各自只从头走到尾、不回头,是 O(m + n),被排序开销盖过
- 空间：O(1) 辅助 · 排序内部因语言而异，不额外开数组,只用几个指针变量,辅助空间 O(1)。排序内部开销因语言而异:C 加加和 Java 通常是 O(log m + log n) 级的递归栈,Python 的排序最坏可到 O(m + n);若把排序内部也算上,空间随语言在这两档之间
易错点
面试追问把动画讲成自己的话
追问这题的核心思路一句话怎么说?
追问为什么这个贪心是对的,能证明吗?
追问复杂度是多少,瓶颈在哪?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
追加字符以获得子序列
LeetCode 2486 · 中等 · 沿着 双指针套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题