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 the maximum number of matchings between players
and trainers
that 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 <= 105
1 <= players[i], trainers[j] <= 109
Solution: Sort + Two Pointers
Sort players and trainers.
Loop through players, skip trainers until he/she can match the current players.
Time complexity: O(nlogn + mlogm + n + m)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
// Author: Huahua class Solution { public: int matchPlayersAndTrainers(vector<int>& players, vector<int>& trainers) { sort(begin(players), end(players)); sort(begin(trainers), end(trainers)); const int n = players.size(); const int m = trainers.size(); int ans = 0; for (int i = 0, j = 0; i < n && j < m; ++i) { while (j < m && players[i] > trainers[j]) ++j; if (j++ == m) break; ++ans; } return ans; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment