2410. Maximum Matching of Players With Trainers

Description

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

The i^th player can match with the j^th trainer if the player's ability is less than or equal to the trainer's training capacity. Additionally, the i^th player can be matched with at most one trainer, and the j^th 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 <= 10⁵
1 <= players[i], trainers[j] <= 10⁹

Solutions

Solution 1: Greedy + Two Pointers

Sort the athletes by their abilities in ascending order, and select the trainer with the smallest ability that is greater than or equal to the athlete’s ability.

The time complexity is $O(n \times \log n + m \times \log m)$, and the space complexity is $O(\log n + \log m)$. Here, $n$ and $m$ are the number of athletes and trainers, respectively.

Solution 2: Greedy + Two Pointers (Iterate over Trainers)

Thinking

Solution 1 still walks past trainers who are too weak for the current player, and returns early once no trainer remains. Moving the outer loop onto the trainers removes that inner scan and the early return.

Sort both arrays and go through the trainers from weakest to strongest, keeping a pointer on the weakest unmatched player. A trainer too weak for that player is too weak for everyone left, and is skipped; a trainer strong enough produces one match and the pointer advances. The pointer’s final value is the answer, and the complexity is unchanged.

Sort players and trainers by ability in non-decreasing order. Pointer $j$ marks the weakest unmatched player and starts at $0$.

Go through the trainers from weakest to strongest. If some player is still unmatched and that player’s ability does not exceed the trainer’s capacity, count one match and increment $j$. Otherwise this trainer cannot match any remaining player and is skipped. After the scan, $j$ is the maximum number of matches.

The time complexity is $O(m \times \log m + n \times \log n)$, and the space complexity is $O(\max(\log m, \log n))$, where $m$ and $n$ are the numbers of players and trainers, respectively.

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


// Solution 2
class Solution {
    public int matchPlayersAndTrainers(int[] players, int[] trainers) {
        Arrays.sort(players);
        Arrays.sort(trainers);
        int j = 0, m = players.length;
        for (int t : trainers) {
            if (j < m && players[j] <= t) {
                ++j;
            }
        }
        return j;
    }
}

class Solution {
public:
    int matchPlayersAndTrainers(vector<int>& players, vector<int>& trainers) {
        sort(players.begin(), players.end());
        sort(trainers.begin(), trainers.end());
        int ans = 0, j = 0;
        for (int p : players) {
            while (j < trainers.size() && trainers[j] < p) {
                ++j;
            }
            if (j < trainers.size()) {
                ++ans;
                ++j;
            }
        }
        return ans;
    }
};


// Solution 2
class Solution {
public:
    int matchPlayersAndTrainers(vector<int>& players, vector<int>& trainers) {
        ranges::sort(players);
        ranges::sort(trainers);
        int j = 0, m = players.size();
        for (int t : trainers) {
            if (j < m && players[j] <= t) {
                ++j;
            }
        }
        return j;
    }
};

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



# Solution 2
class Solution:
    def matchPlayersAndTrainers(self, players: List[int], trainers: List[int]) -> int:
        players.sort()
        trainers.sort()
        j = 0
        for t in trainers:
            if j < len(players) and players[j] <= t:
                j += 1
        return j

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


// Solution 2
func matchPlayersAndTrainers(players []int, trainers []int) int {
	sort.Ints(players)
	sort.Ints(trainers)
	j, m := 0, len(players)
	for _, t := range trainers {
		if j < m && players[j] <= t {
			j++
		}
	}
	return j
}

function matchPlayersAndTrainers(players: number[], trainers: number[]): number {
    players.sort((a, b) => a - b);
    trainers.sort((a, b) => a - b);
    const [m, n] = [players.length, trainers.length];
    for (let i = 0, j = 0; i < m; ++i, ++j) {
        while (j < n && trainers[j] < players[i]) {
            ++j;
        }
        if (j === n) {
            return i;
        }
    }
    return m;
}



// Solution 2
function matchPlayersAndTrainers(players: number[], trainers: number[]): number {
    players.sort((a, b) => a - b);
    trainers.sort((a, b) => a - b);
    let j = 0;
    const m = players.length;
    for (const t of trainers) {
        if (j < m && players[j] <= t) {
            ++j;
        }
    }
    return j;
}

impl Solution {
    pub fn match_players_and_trainers(mut players: Vec<i32>, mut trainers: Vec<i32>) -> i32 {
        players.sort();
        trainers.sort();
        let mut j = 0;
        let n = trainers.len();
        for (i, &p) in players.iter().enumerate() {
            while j < n && trainers[j] < p {
                j += 1;
            }
            if j == n {
                return i as i32;
            }
            j += 1;
        }
        players.len() as i32
    }
}



// Solution 2
impl Solution {
    pub fn match_players_and_trainers(mut players: Vec<i32>, mut trainers: Vec<i32>) -> i32 {
        players.sort();
        trainers.sort();
        let mut j = 0;
        for &t in &trainers {
            if j < players.len() && players[j] <= t {
                j += 1;
            }
        }
        j as i32
    }
}

2410 - Maximum Matching of Players With Trainers

2410. Maximum Matching of Players With Trainers

Description

Solutions

Solution 2: Greedy + Two Pointers (Iterate over Trainers)

All Problems

All Solutions

Welcome to Subscribe On Youtube

2410. Maximum Matching of Players With Trainers

Description

Solutions

Solution 2: Greedy + Two Pointers (Iterate over Trainers)

All Problems

All Solutions