Maximum Matching of Players With Trainers

Medium
1448.

Maximum Matching of Players With Trainers

Maximum Matching of Players With Trainers is a medium coding problem on arrays, sorting and greedy, asked in Amazon and Google interviews.

players[i] is the ability of player i and trainers[j] the training capacity of trainer j.

Player i can be matched with trainer j when players[i] <= trainers[j]. Every player can be matched with at most one trainer, and every trainer with at most one player.

Return the maximum number of matchings.

Example 1

Input
players = [3,1,6], trainers = [2,6,4,1]
Output
3
Explanation
1 with 1, 3 with 4, 6 with 6.

Example 2

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

Example 3

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

Constraints

  • 1 <= players.length, trainers.length <= 10^5
  • 1 <= players[i], trainers[j] <= 10^9
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} players
 * @param {number[]} trainers
 * @return {number}
 */
var matchPlayersAndTrainers = function(players, trainers) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Maximum Matching of Players With Trainers — Solution

Maximum Matching of Players With Trainers solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Maximum Matching of Players With Trainers is a medium coding problem on arrays, sorting and greedy, asked in Amazon and Google interviews.

  • Difficulty: Medium
  • Topics: Arrays, Sorting, Greedy, Two Pointers
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

players[i] is the ability of player i and trainers[j] the training capacity of trainer j.

Player i can be matched with trainer j when players[i] <= trainers[j]. Every player can be matched with at most one trainer, and every trainer with at most one player.

Return the maximum number of matchings.

Example 1

Input: players = [3,1,6], trainers = [2,6,4,1]
Output: 3
Explanation: 1 with 1, 3 with 4, 6 with 6.

Example 2

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

Example 3

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

Constraints

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

Hints for Maximum Matching of Players With Trainers

  1. Hint 1

    The weakest player is the easiest to place; the weakest trainer is the most constrained.

  2. Hint 2

    Sort both arrays.

  3. Hint 3

    Walk them with two pointers: if the current trainer can take the current player, match them and advance both; otherwise this trainer is too weak for everyone left — skip it.

How to solve Maximum Matching of Players With Trainers

Give each player, from weakest to strongest, the weakest trainer that can still handle them. Two pointers over the sorted arrays implement it in one pass.

Approach

  1. Sort players and trainers ascending.
  2. Set i = j = matched = 0.
  3. While both pointers are in range: if players[i] <= trainers[j], match them (matched++, i++, j++); otherwise j++.
  4. Return matched.

Why it works

A trainer too weak for the current (weakest unmatched) player is too weak for every later player, so skipping it loses nothing. When the trainer fits, pairing it with the weakest player is safe by exchange: in any optimal matching, swapping partners so that the weakest player takes the weakest usable trainer keeps every pair valid, because the stronger trainer it frees is at least as capable.

Complexity

  • Time — O(n log n + m log m)
  • Space — O(1) beyond the sorts

Pitfalls

  • The condition is player <= trainer; equality counts as a match.
  • Advance only the trainer pointer when a trainer is too weak — the player still needs one.
  • Matching the strongest player first with the strongest trainer also works; mixing directions does not.

Reference solution

Python

from typing import List

def matchPlayersAndTrainers(players: List[int], trainers: List[int]) -> int:
    p, t = sorted(players), sorted(trainers)
    i = j = matched = 0
    while i < len(p) and j < len(t):
        if p[i] <= t[j]:
            matched += 1
            i += 1
        j += 1
    return matched

Java

public static int matchPlayersAndTrainers(int[] players, int[] trainers) {
    int[] p = players.clone(), t = trainers.clone();
    Arrays.sort(p);
    Arrays.sort(t);
    int i = 0, j = 0, matched = 0;
    while (i < p.length && j < t.length) {
        if (p[i] <= t[j]) {
            matched++;
            i++;
        }
        j++;
    }
    return matched;
}

C++

int matchPlayersAndTrainers(vector<int>& players, vector<int>& trainers) {
    vector<int> p = players, t = trainers;
    sort(p.begin(), p.end());
    sort(t.begin(), t.end());
    size_t i = 0, j = 0;
    int matched = 0;
    while (i < p.size() && j < t.size()) {
        if (p[i] <= t[j]) {
            matched++;
            i++;
        }
        j++;
    }
    return matched;
}

JavaScript

var matchPlayersAndTrainers = function(players, trainers) {
    var p = players.slice().sort(function(a, b) { return a - b; });
    var t = trainers.slice().sort(function(a, b) { return a - b; });
    var i = 0, j = 0, matched = 0;
    while (i < p.length && j < t.length) {
        if (p[i] <= t[j]) {
            matched++;
            i++;
        }
        j++;
    }
    return matched;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Sorting Algorithms