Coding · Greedy
Maximum Matching of Players With Trainers
- Reported in several places
- Medium
- L4
- 2 sources
Two or more independent public pages, at least one a candidate write-up.
Solve it in the playground, with tests
Each player has an ability and each trainer has a capacity. A trainer can train a player only when the capacity is at least the ability, and everyone can be in at most one pair, so return the largest number of pairs you can form. For example, players [4,7,9] and trainers [8,2,5,8] give 2. Each array holds up to 100,000 integers.
Restated in our own words, not a quote from Google or any page. The answer below is written for this site.
Clarify first
Pin down the input before you touch the keyboard.
I would ask: does "at least" mean equal values can be paired? (Yes.) Is each trainer limited to one player? Are the arrays sorted? Can either be empty? Are values large or negative? Do I return only the count, or also the pairs? Can I change the input arrays?
Assumptions I would state: equal ability and capacity can pair, one player per trainer and one trainer per player, unsorted input, either array may be empty (answer 0), I return the count only, and I will not modify the caller's arrays, so I work on sorted copies.
Brute force
Say the obvious answer and why it is too slow.
The exhaustive approach tries every way to assign trainers to players: for each player, either skip them or pair them with any unused trainer that is strong enough, and keep the best count. It is correct, but exponential, roughly as many branches as there are partial matchings. It cannot handle even 30 players, never mind 100,000.
The tempting shortcut is first fit: go through the players in the given order and give each one the first unused trainer who can handle them. That is fast but wrong. With players [4,7] and trainers [8,5], player 4 grabs trainer 8, and player 7 is left with nobody, so the count is 1. Pairing 4 with 5 and 7 with 8 gives 2. A strong trainer was wasted on a weak player.
The insight
The one idea that makes it fast, and why it is correct.
- Brute force
- Exponential in n
- Time
- O(n log n + m log m)
- Space
- O(n + m) for the sorted copies
The pattern is greedy: sort both sides, then two pointers. Sort players by ability and trainers by capacity, both ascending. Then compare the weakest unmatched player with the weakest unused trainer. If the trainer is strong enough, pair them. If not, that trainer is too weak for this player, and since this is the weakest player left, too weak for everyone, so throw the trainer away. Either way move the trainer pointer forward. The player pointer only moves when a pair is made, so its final value is the answer.
Why is the greedy choice safe? An exchange argument. Let w be the weakest player and t the weakest trainer who can handle w. Take any best solution. If w is paired with some trainer t2 (stronger than or equal to t), and t is paired with another player x, swap them: w goes with t, and x goes with t2. This is valid because t could handle x, and t2 is at least as strong as t. If t is unused, move w to t. If w is unpaired and t is paired with x, replace x by w. In every case the count does not drop, so some best solution contains the pair (w, t). Remove both and repeat on the smaller problem.
Out loud: "Weakest player gets the weakest trainer who can do the job. That never hurts, because the stronger trainers are worth more to the stronger players." Sorting is the dominant cost.
Walk it through
A dry run on the example, step by step.
| Step | Trainer | Waiting player | Decision | Pairs so far |
|---|---|---|---|---|
| 1 | 2 | 4 | 2 < 4, drop trainer | 0 |
| 2 | 5 | 4 | 5 >= 4, pair them | 1 |
| 3 | 8 | 7 | 8 >= 7, pair them | 2 |
| 4 | 8 | 9 | 8 < 9, drop trainer | 2 |
| 5 | none left | 9 | trainers exhausted | 2 |
Sorted, the players are [4,7,9] and the trainers are [2,5,8,8]. The table shows each trainer in turn against the weakest waiting player.
Trainer 2 cannot handle player 4, so the trainer is dropped and the player keeps waiting. Trainer 5 can handle 4, so that is the first pair, and both pointers move. Trainer 8 against player 7 is a second pair. The last trainer, 8, faces player 9, who needs more than 8, so this trainer is dropped, and the trainers run out. The player pointer stopped at 2, so the answer is 2. Note that the player with ability 9 could not be paired by anyone here, since no trainer has capacity above 8.
The code
Runnable JavaScript, checked against test cases.
function matchPlayersAndTrainers(players, trainers) {
const abilities = [...players].sort((a, b) => a - b);
const capacities = [...trainers].sort((a, b) => a - b);
let nextPlayer = 0;
let nextTrainer = 0;
while (nextPlayer < abilities.length && nextTrainer < capacities.length) {
if (abilities[nextPlayer] <= capacities[nextTrainer]) {
nextPlayer++;
}
nextTrainer++;
}
return nextPlayer;
}Runs here in your browser, in a sandboxed worker. Nothing is sent anywhere.
Try your own input
Write JavaScript that calls the code above and prints with console.log. It runs after the solution.
Edge cases
What to test before you say you are done.
Either array empty: the loop condition fails at once and the answer is 0.
- Equal values: the check uses less-than-or-equal, so ability 5 pairs with capacity 5.
- All trainers too weak: the trainer pointer runs off the end with zero pairs.
- More players than trainers, or the reverse: the loop stops when either side is exhausted.
- Duplicates: each copy is a separate player or trainer and pairs on its own.
- Unsorted input: sorting copies makes the order irrelevant and leaves the caller's arrays alone.
- Large values: only comparisons are made, so there is no overflow.
Follow-ups to expect
Where the interviewer pushes next.
- What changes if each trainer can train two players?
- What if each pair earns a score and you want the highest total instead of the most pairs?
- Could you scan from the strongest player and strongest trainer instead, and would the answer stay the same?
- How would you avoid the sort if all abilities and capacities were small integers?
- How is this related to handing out cookies to children, or to assigning jobs to machines?
Where candidates slip
The mistakes this problem punishes.
The most common slip is first fit on the unsorted input, which wastes strong trainers on weak players and gives a wrong count.
- Sorting only one of the two arrays.
- Calling
sort()with no comparator, so numbers are compared as text and 10 sorts before 9. - Using a strict less-than, which refuses equal pairs.
- Advancing both pointers every time, even on a failed comparison, which throws away a player who could still be matched.
- Giving the strongest trainer to the weakest player.
- Returning the trainer pointer instead of the player pointer.
- Sorting the caller's arrays in place without meaning to.
Have a go before you read.
Interviews reward the sketch you make cold. Clarify out loud, draw it, then compare with the answer.
Now make it stick
Where this was reported
Public pages only. Companies do not confirm these, and they rotate their questions, so treat each link as one person's account or one list's tag.