Watch 10 video solutions for Maximum Matching of Players With Trainers, a medium level problem involving Array, Two Pointers, Greedy. This walkthrough by codestorywithMIK has 4,026 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 1051 <= players[i], trainers[j] <= 109
Note: This question is the same as 445: Assign Cookies.
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 | 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 |