2410. 运动员和训练师的最大匹配数

🟠   🔖  贪心 数组 双指针 排序  🔗 力扣 LeetCode

题目

You are given a 0-indexed integer array players, where players[i] represents the ability of the ith player. You are also given a 0-indexed integer array trainers, where trainers[j] represents the training capacity of the jth trainer.

The ith player can match with the jth trainer if the player's ability is less than or equal to the trainer's training capacity. Additionally, the ith player can be matched with at most one trainer, and the jth trainer can be matched with at most one player.

Return _themaximum number of matchings between _players andtrainersthat satisfy these conditions.

Example 1:

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

Output: 2

Explanation:

One of the ways we can form two matchings is as follows:

• players[0] can be matched with trainers[0] since 4 <= 8.
• players[1] can be matched with trainers[3] since 7 <= 8.

It can be proven that 2 is the maximum number of matchings that can be formed.

Example 2:

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

Output: 1

Explanation:

The trainer can be matched with any of the 3 players.

Each player can only be matched with one trainer, so the maximum answer is 1.

Constraints:

• 1 <= players.length, trainers.length <= 10^5
• 1 <= players[i], trainers[j] <= 10^9

Note: This question is the same as 455. Assign Cookies

题目大意

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

解题思路

为了最大化满足运动员的需求，可以采用贪心算法来解决这个问题。

1. 排序：首先，对运动员的能力值数组 g 和训练师的能力值数组 s 进行排序。排序后，可以依次尝试给每个运动员分配能力值最小的满足条件的训练师。
2. 使用两个指针 i 和 j 分别遍历运动员和训练师数组，对于每个运动员，尝试找到一个符合条件（即训练师能力值大于等于运动员能力值）的训练师：
   • 如果 s[j] >= g[i]，就给运动员 i 分配训练师 j，然后 i++ 和 j++。
   • 如果 s[j] < g[i]，则当前训练师无法满足运动员，j++，尝试下一个训练师。
   • 当没有更多的运动员或训练师时，就停止。
3. 最后返回分配的训练师数量 count。

复杂度分析

• 时间复杂度：O(n log n)。
  • 排序需要 O(n log n) 时间，其中 n 是运动员或训练师数组的长度。
  • 遍历数组需要 O(n) 时间。
  • 总时间复杂度为 O(n log n)，因为排序是最耗时的操作。
• 空间复杂度：O(1)，只使用了常数空间来存储一些指针和计数器。

代码

/**
 * @param {number[]} players
 * @param {number[]} trainers
 * @return {number}
 */
var matchPlayersAndTrainers = function (players, trainers) {
	// 排序运动员的能力值和训练师的能力值
	players.sort((a, b) => a - b);
	trainers.sort((a, b) => a - b);

	let count = 0,
		i = 0,
		j = 0;

	// 遍历运动员和训练师
	while (i < players.length && j < trainers.length) {
		// 如果当前训练师可以满足当前运动员，分配训练师
		if (players[i] <= trainers[j]) {
			count++;
			i++; // 满足该运动员
		}
		j++; // 继续查看下一个训练师
	}
	return count;
};

相关题目

题号	标题	题解	标签	难度	力扣
826	安排工作以达到最大收益		贪心 数组 双指针 2+	🟠	🀄️ 🔗
925	长按键入	[✓]	双指针 字符串	🟢	🀄️ 🔗
986	区间列表的交集	[✓]	数组 双指针	🟠	🀄️ 🔗
1754	构造字典序最大的合并字符串		贪心 双指针 字符串	🟠	🀄️ 🔗
2071	你可以安排的最多任务数目		贪心 队列 数组 3+	🔴	🀄️ 🔗
2300	咒语和药水的成功对数	[✓]	数组 双指针 二分查找 1+	🟠	🀄️ 🔗
2332	坐上公交的最晚时间		数组 双指针 二分查找 1+	🟠	🀄️ 🔗
2592	最大化数组的伟大值		贪心 数组 双指针 1+	🟠	🀄️ 🔗