What is the brute force approach and complexity for Maximum Matching of Players With Trainers?

Backtrack over the players: each one gets no trainer, or any free trainer that is strong enough with time complexity O((M + 1)^N) and space complexity O(N + M).

What is the optimal approach and complexity for Maximum Matching of Players With Trainers?

Sort both lists. Walk the trainers from weakest; each one takes the weakest waiting player it can train with optimal time complexity O(N log N + M log M) and space complexity O(1).

How do you identify the pattern for Maximum Matching of Players With Trainers?

Look for key signals in the prompt: "each player is matched with at most one trainer" indicates A one-to-one pairing, the same as Assign Cookies.; "ability is at most the training capacity" indicates A one-sided threshold: a trainer works for every player weak enough.; "maximum number of matchings" indicates Count the pairs. Use the weakest trainer that works for the weakest waiting player..

Maximum Matching of Players With Trainers

Medium·LeetCode #2410 Pro OnlyBasic Reinforcement

LeetCode

Problem Statement

Each player has an ability, and each trainer has a capacity: the highest ability they can train.

A player can be matched with a trainer only if the player's ability is at most the trainer's capacity. Each player can be matched with at most one trainer, and each trainer can take at most one player.

Make as many matches as you can. Return that number.

Input

players, the ability of each player, and trainers, the capacity of each trainer.

Output

One integer: the largest number of player–trainer matches.

Example 1

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

Output: 2

Match the ability-4 player with a capacity-8 trainer, and the ability-7 player with the other capacity-8 trainer. The ability-9 player is too strong for every trainer.

Example 2

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

Output: 1

One trainer can take only one player, so the answer is 1.

Constraints

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

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“each player is matched with at most one trainer”

→ A one-to-one pairing, the same as Assign Cookies.

“ability is at most the training capacity”

→ A one-sided threshold: a trainer works for every player weak enough.

“maximum number of matchings”

→ Count the pairs. Use the weakest trainer that works for the weakest waiting player.

Approach Complexity Ladder

Brute Force — try every set of matchesO((M + 1)^N)O(N + M)

Backtrack over the players: each one gets no trainer, or any free trainer that is strong enough

Optimal — sort both, then walk the trainers onceO(N log N + M log M)O(1)

Sort both lists. Walk the trainers from weakest; each one takes the weakest waiting player it can train

Brute Force Intuition

Go through the players in order. For each one, try no trainer, and try each unused trainer whose capacity is at least the player's ability. Keep the largest number of matches over all these choices.

Recognition rule for this sub-pattern:

Sort both sides and match the smallest that works, so bigger resources stay free.

Remember this · Greedy

Trigger

Maximise count / minimise cost with a natural "best next step", sorting makes the choice obvious, reachability.

Think

Is there a choice I can always make safely without looking ahead?

Key question

Why can't the greedy choice be worse than the optimal one? (Try to break it with a small example.)

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Greedy translate into production architectures and low-level memory mechanics.

LLD Architecture