Maximum Matching of Players With Trainers

Maximum Matching of Players With Trainers

What is this problem about?

The Maximum Matching of Players With Trainers coding problem gives you two arrays: player abilities and trainer capacities. A player can be matched with a trainer if the player's ability is less than or equal to the trainer's capacity. Each player and trainer can be in at most one match. Maximize the number of matched pairs.

Why is this asked in interviews?

Meta, Amazon, and Google include this problem because it is a clean application of greedy two-pointer technique after sorting. It directly mirrors the classic "assign tasks to workers with capacity constraints" pattern. Candidates who recognize this as a bipartite matching problem solvable greedily (without complex matching algorithms) because of the sorted order demonstrate strong pattern recognition.

Algorithmic pattern used

Greedy with two pointers after sorting: Sort both arrays. Use two pointers p (players) and t (trainers). If players[p] <= trainers[t], match them: increment both pointers and count. Otherwise, move the trainer pointer forward (current trainer is too weak for this player, but a stronger trainer might work). This greedy works because sorted order ensures we always try the weakest available trainer that can handle the current (weakest unmatched) player.

Time: O(n log n + m log m) for sorting, O(n + m) for the two-pointer scan.

Example explanation

Players: [4, 7, 9], Trainers: [8, 2, 5, 10]

• Sort players: [4, 7, 9]. Sort trainers: [2, 5, 8, 10].
• p=0(4), t=0(2): 4 > 2. Move t → t=1.
• p=0(4), t=1(5): 4 ≤ 5. Match! Count=1. p=1, t=2.
• p=1(7), t=2(8): 7 ≤ 8. Match! Count=2. p=2, t=3.
• p=2(9), t=3(10): 9 ≤ 10. Match! Count=3. p=3.
• Answer = 3.

Common mistakes candidates make

• Not sorting both arrays: The greedy only works correctly on sorted inputs. Unsorted arrays lead to suboptimal matches.
• Moving the player pointer when unmatched: When a trainer is too weak, you should advance the trainer pointer, not the player pointer. Players are matched in order of ability.
• Using complex bipartite matching: This problem doesn't need Hopcroft-Karp or Hungarian algorithm — the greedy works because constraints are monotone after sorting.

Interview preparation tip

For the Array Sorting Two Pointers Greedy interview pattern, remember this rule: "sort both arrays, match the weakest valid pair first." This pattern — two sorted arrays, one-to-one matching with a capacity constraint — appears frequently in scheduling, resource allocation, and pairing interview problems. It always yields an O(n log n) greedy solution.