2410. Max Matching of Players With Trainers Solution

The problem

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⁹

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

Approach overview

Problem Overview: You have two arrays: players representing player ability and trainers representing trainer capacity. A trainer can train one player only if trainer >= player. Each trainer can be used once. The task is to maximize the number of valid player‑trainer matches.

Approach 1: Two-Pointer Technique after Sorting (O(n log n) time, O(1) extra space)

Sort both arrays, then greedily match the smallest available player with the smallest trainer that can handle them. Use two pointers: one for players and one for trainers. If the current trainer capacity is greater than or equal to the player's ability, record a match and move both pointers. Otherwise move only the trainer pointer to search for a stronger trainer. Sorting ensures you never waste a high-capacity trainer on a weak player when a smaller trainer could work. The algorithm performs a single linear scan after sorting, making it efficient and easy to implement using concepts from sorting, two pointers, and greedy algorithms.

Approach 2: Greedy Matching with Ordered Sets (O(n log n) time, O(n) space)

Insert all trainer capacities into an ordered structure such as a multiset (C++) or bisect/sorted container style structure in Python. Iterate through players and find the smallest trainer whose capacity is at least the player's ability using a lower_bound-style lookup. If such a trainer exists, match them and remove that trainer from the set so it cannot be reused. Each lookup and removal takes O(log n), and you perform it for each player. This approach is useful when you want explicit control over matching or when processing players in a custom order.

The key greedy insight is that weaker players should consume the weakest valid trainers. Assigning a large-capacity trainer too early can block a future player who actually needs that capacity. Sorting or ordered lookups guarantee that each match uses the smallest feasible trainer.

Recommended for interviews: The sorted two-pointer approach is the expected solution. It is short, easy to reason about, and clearly demonstrates greedy thinking combined with efficient iteration over arrays. Interviewers typically expect O(n log n) due to sorting, followed by a linear scan. The ordered set method shows deeper knowledge of data structures but is rarely necessary unless the problem introduces dynamic updates.

Approach 1: Two-Pointer Technique after Sorting

This approach involves sorting both the players and trainers arrays. Then, using a two-pointer method, we try to find the maximum number of pairings possible. We move pointers on players and trainers based on the comparison between the player's ability and the trainer's capacity.

Python

def maxMatchings(players, trainers):
    players.sort()
    trainers.sort()
    i = j = matches = 0
    while i < len(players) and j < len(trainers):
        if players[i] <= trainers[j]:
            matches += 1
            i += 1
        j += 1
    return matches

players = [4, 7, 9]
trainers = [8, 2, 5, 8]
print(maxMatchings(players, trainers))

Java

import java.util.Arrays;

public class MaximumMatchings {
    public static int maxMatchings(int[] players, int[] trainers) {
        Arrays.sort(players);
        Arrays.sort(trainers);
        int i = 0, j = 0, matches = 0;
        while (i < players.length && j < trainers.length) {
            if (players[i] <= trainers[j]) {
                matches++;
                i++;
            }
            j++;
        }
        return matches;
    }

    public static void main(String[] args) {
        int[] players = {4, 7, 9};
        int[] trainers = {8, 2, 5, 8};
        System.out.println(maxMatchings(players, trainers));
    }
}

C++

#include <iostream>
#include <vector>
#include <algorithm>

int maxMatchings(std::vector<int>& players, std::vector<int>& trainers) {
    std::sort(players.begin(), players.end());
    std::sort(trainers.begin(), trainers.end());
    int i = 0, j = 0, matches = 0;
    while (i < players.size() && j < trainers.size()) {
        if (players[i] <= trainers[j]) {
            matches++;
            i++;
        }
        j++;
    }
    return matches;
}

int main() {
    std::vector<int> players = {4, 7, 9};
    std::vector<int> trainers = {8, 2, 5, 8};
    std::cout << maxMatchings(players, trainers) << std::endl;
    return 0;
}

JavaScript

function maxMatchings(players, trainers) {
    players.sort((a, b) => a - b);
    trainers.sort((a, b) => a - b);
    let i = 0, j = 0, matches = 0;
    while (i < players.length && j < trainers.length) {
        if (players[i] <= trainers[j]) {
            matches++;
            i++;
        }
        j++;
    }
    return matches;
}

let players = [4, 7, 9];
let trainers = [8, 2, 5, 8];
console.log(maxMatchings(players, trainers));

#include <stdio.h>
#include <stdlib.h>

int compare(const void* a, const void* b) {
    return *(int*)a - *(int*)b;
}

int maxMatchings(int* players, int playersSize, int* trainers, int trainersSize){
    qsort(players, playersSize, sizeof(int), compare);
    qsort(trainers, trainersSize, sizeof(int), compare);
    
    int i = 0, j = 0, matches = 0;
    while (i < playersSize && j < trainersSize) {
        if (players[i] <= trainers[j]) {
            matches++;
            i++;
        }
        j++;
    }
    return matches;
}

int main() {
    int players[] = {4, 7, 9};
    int trainers[] = {8, 2, 5, 8};
    int maxMatches = maxMatchings(players, 3, trainers, 4);
    printf("%d\n", maxMatches);
    return 0;
}

using System;

public class MaximumMatchings {
    public static int MaxMatchings(int[] players, int[] trainers) {
        Array.Sort(players);
        Array.Sort(trainers);
        int i = 0, j = 0, matches = 0;
        while (i < players.Length && j < trainers.Length) {
            if (players[i] <= trainers[j]) {
                matches++;
                i++;
            }
            j++;
        }
        return matches;
    }

    public static void Main() {
        int[] players = {4, 7, 9};
        int[] trainers = {8, 2, 5, 8};
        Console.WriteLine(MaxMatchings(players, trainers));
    }
}

In this Python solution, sorting is applied to both input arrays. Using two pointers, the function iterates through both arrays, pairing a player with a trainer whenever the player's ability does not exceed the trainer's capacity.

Complexity

Time Complexity: O(n log n + m log m).
Space Complexity: O(1).

Try this approach in the editor

Approach 2: Greedy Matching with Sets

This approach is based on using a greedy algorithm with the help of sets or heaps to facilitate a similar matching process. By leveraging the properties of sets, we can efficiently manage player-trainer pairings as we iterate through sorted lists.

Python

import bisect

def maxMatchings(players, trainers):
    players.sort()
    trainers.sort()
    matches = 0
    for player in players:
        pos = bisect.bisect_left(trainers, player)
        if pos < len(trainers):
            matches += 1
            trainers.pop(pos)
    return matches

players = [4, 7, 9]
trainers = [8, 2, 5, 8]
print(maxMatchings(players, trainers))

C++

#include <iostream>
#include <set>
#include <vector>
#include <algorithm>

int maxMatchings(std::vector<int>& players, std::vector<int>& trainers) {
    std::multiset<int> trainerSet(trainers.begin(), trainers.end());
    std::sort(players.begin(), players.end());
    int matches = 0;
    for (int player : players) {
        auto it = trainerSet.lower_bound(player);
        if (it != trainerSet.end()) {
            matches++;
            trainerSet.erase(it);
        }
    }
    return matches;
}

int main() {
    std::vector<int> players = {4, 7, 9};
    std::vector<int> trainers = {8, 2, 5, 8};
    std::cout << maxMatchings(players, trainers) << std::endl;
    return 0;
}

This Python solution uses the bisect module to perform binary search-like operations on trainers. This allows us to efficiently find eligible trainers for each player. This approach removes trainers once they are matched, ensuring they're not reused.

Complexity

Time Complexity: O(n log n + m log m) for sorting and matching.
Space Complexity: O(n + m) to store players and trainers.

Try this approach in the editor

Approach 3: Greedy + Two Pointers

According to the problem description, each athlete should be matched with the trainer whose ability value is as close as possible. Therefore, we can sort the ability values of both athletes and trainers, and then use the two-pointer method for matching.

We use two pointers i and j to point to the arrays of athletes and trainers, respectively, both initially pointing to the start of the arrays. Then we traverse the ability values of the athletes one by one. If the current trainer's ability value is less than the current athlete's ability value, we move the trainer's pointer to the right by one position until we find a trainer whose ability value is greater than or equal to the current athlete's. If no such trainer is found, it means the current athlete cannot be matched with any trainer, and we return the current athlete's index. Otherwise, we can match the current athlete with the trainer, and then move both pointers to the right by one position. Continue this process until all athletes have been traversed.

If we traverse all athletes, it means all athletes can be matched with trainers, and we return the number of athletes.

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

TypeScript

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;
}

func matchPlayersAndTrainers(players []int, trainers []int) int {
	sort.Ints(players)
	sort.Ints(trainers)
	m, n := len(players), len(trainers)
	for i, j := 0, 0; i < m; i, j = i+1, j+1 {
		for j < n && trainers[j] < players[i] {
			j++
		}
		if j == n {
			return i
		}
	}
	return m
}

Rust

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
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Two-Pointer Technique after Sorting	Time Complexity: O(n log n + m log m). Space Complexity: O(1).
Greedy Matching with Sets	Time Complexity: O(n log n + m log m) for sorting and matching. Space Complexity: O(n + m) to store players and trainers.
Greedy + Two Pointers	–

Complexity analysis

Approach	Time	Space	When to Use
Two-Pointer Technique after Sorting	O(n log n)	O(1)	Best general solution; simple greedy matching after sorting both arrays
Greedy Matching with Ordered Set	O(n log n)	O(n)	Useful when trainers must be searched dynamically using lower_bound lookups

Frequently asked questions

Is Maximum Matching of Players With Trainers easy or hard?

The problem is rated Medium because the greedy idea must be recognized. Once you realize that weaker players should use the smallest valid trainers, the implementation becomes straightforward with sorting and two pointers.

Maximum Matching of Players With Trainers Python/Java solution

In Python or Java, sort both arrays and iterate with two indices. When trainer >= player, increment the match count and move both pointers; otherwise move the trainer pointer. This greedy scan produces the maximum number of valid matches in O(n log n) time.

How to solve Maximum Matching of Players With Trainers in O(n)?

True O(n) time is generally not achievable because the arrays are unsorted and require ordering to guarantee optimal greedy matching. The best practical solution is O(n log n) using sorting followed by a linear two-pointer pass.

What is the best approach for Maximum Matching of Players With Trainers?

The optimal solution sorts both players and trainers, then uses a greedy two-pointer scan. Always try to match the smallest player with the smallest trainer capable of training them. This avoids wasting stronger trainers early. The complexity is O(n log n) due to sorting and O(1) extra space.

Is Maximum Matching of Players With Trainers asked at Google/Amazon/Meta?

Greedy matching and two-pointer problems like this appear frequently in interviews at companies such as Amazon, Google, and Meta. Variants involving pairing resources with constraints or scheduling tasks are common interview patterns.

What data structure is used in Maximum Matching of Players With Trainers?

The typical solution uses arrays combined with sorting and two pointers. An alternative solution uses ordered data structures such as a multiset or balanced binary search tree to perform lower_bound lookups for the smallest valid trainer.

What is the time complexity of Maximum Matching of Players With Trainers?

The optimal algorithm runs in O(n log n) time because both arrays must be sorted first. After sorting, a single linear scan with two pointers matches players and trainers in O(n). Space complexity can be O(1) if sorting is done in-place.

Maximum Matching of Players With Trainers solution and explanation

The problem

Approach overview

Approach 1: Two-Pointer Technique after Sorting

Approach 2: Greedy Matching with Sets

Approach 3: Greedy + Two Pointers

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Maximum Matching of Players With Trainers solution and explanation

The problem

Approach overview

Approach 1: Two-Pointer Technique after Sorting

Approach 2: Greedy Matching with Sets

Approach 3: Greedy + Two Pointers

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems