2410.运动员和训练师的最大匹配数:贪心(拿当前min教练匹配剩下最min学员)

【LetMeFly】2410.运动员和训练师的最大匹配数:贪心(拿当前min教练匹配剩下最min学员)

力扣题目链接:https://leetcode.cn/problems/maximum-matching-of-players-with-trainers/

给你一个下标从 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 <= 105
  • 1 <= players[i], trainers[j] <= 109

解题方法:贪心(排序)

首先二话不说分别对学员和教练按从小到大的顺序排个序,接着开始遍历教练:

如果最low的(剩余)学员都教不了,这个教练可以回家了;否则就让这个教练教这个最low学员。

why?

当前最low教练能教小菜,也能教小强,教练教小菜是不是浪费了?不浪费,这个教练都能教小菜了,下一个教练更能教小菜。我们只关注被教的学员数量而不关注所教的学员水平。

为何不让小菜选一个超强教练?很显然,因为浪费。超强教练都拿来教小菜了,后面的学员小强就不一定能有教练教了。

  • 时间复杂度$O(n\log n + m\log m)$,其中$n = len(players), m = len(trainers)$
  • 空间复杂度$O(\log n + \log m)$

AC代码

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/*
* @Author: LetMeFly
* @Date: 2025-07-13 16:44:48
* @LastEditors: LetMeFly.xyz
* @LastEditTime: 2025-07-13 16:57:27
*/
/*
拿当前min教练匹配剩下最min学员
*/
class Solution {
public:
int matchPlayersAndTrainers(vector<int>& players, vector<int>& trainers) {
sort(players.begin(), players.end());
sort(trainers.begin(), trainers.end());
int ans = 0;
for (int t = 0, p = 0; t < trainers.size() && p < players.size(); t++) {
if (trainers[t] >= players[p]) {
ans++, p++;
}
}
return ans;
}
};

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
'''
Author: LetMeFly
Date: 2025-07-13 16:44:48
LastEditors: LetMeFly.xyz
LastEditTime: 2025-07-13 17:00:27
'''
from typing import List

class Solution:
def matchPlayersAndTrainers(self, players: List[int], trainers: List[int]) -> int:
players.sort()
trainers.sort()
ans = p = t = 0
while t < len(trainers) and p < len(players):
if trainers[t] >= players[p]:
ans += 1
p += 1
t += 1
return ans

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/*
* @Author: LetMeFly
* @Date: 2025-07-13 16:44:48
* @LastEditors: LetMeFly.xyz
* @LastEditTime: 2025-07-13 17:06:30
*/
import java.util.Arrays;

class Solution {
public int matchPlayersAndTrainers(int[] players, int[] trainers) {
Arrays.sort(players);
Arrays.sort(trainers);
int ans = 0;
for (int p = 0, t = 0; p < players.length && t < trainers.length; t++) {
if (trainers[t] >= players[p]) {
ans++;
p++;
}
}
return ans;
}
}

Go

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/*
* @Author: LetMeFly
* @Date: 2025-07-13 16:44:48
* @LastEditors: LetMeFly.xyz
* @LastEditTime: 2025-07-13 17:08:39
*/
package main

import "sort"

func matchPlayersAndTrainers(players []int, trainers []int) (ans int) {
sort.Ints(players)
sort.Ints(trainers)
for p, t := 0, 0; p < len(players) && t < len(trainers); t++ {
if trainers[t] >= players[p] {
ans++
p++
}
}
return
}

同步发文于CSDN和我的个人博客,原创不易,转载经作者同意后请附上原文链接哦~

千篇源码题解已开源


2410.运动员和训练师的最大匹配数:贪心(拿当前min教练匹配剩下最min学员)
https://blog.letmefly.xyz/2025/07/13/LeetCode 2410.运动员和训练师的最大匹配数/
作者
发布于
2025年7月13日
许可协议