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 |
|
Python
1 |
|
Java
1 |
|
Go
1 |
|
同步发文于CSDN和我的个人博客,原创不易,转载经作者同意后请附上原文链接哦~
千篇源码题解已开源
2410.运动员和训练师的最大匹配数:贪心(拿当前min教练匹配剩下最min学员)
https://blog.letmefly.xyz/2025/07/13/LeetCode 2410.运动员和训练师的最大匹配数/