Maximum Matching of Players With Trainers

Maximum Matching of Players With Trainers - Problem

You are given a 0-indexed integer array players, where players[i] represents the ability of the i^th player. You are also given a 0-indexed integer array trainers, where trainers[j] represents the training capacity of the j^th trainer.

The i^th player can match with the j^th trainer if the player's ability is less than or equal to the trainer's training capacity. Additionally, the i^th player can be matched with at most one trainer, and the j^th trainer can be matched with at most one player.

Return the maximum number of matchings between players and trainers that satisfy these conditions.

Input & Output

Example 1 — Basic Case

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

› Output: 2

💡 Note: We can match player 4 with trainer 5 (4 ≤ 5) and player 7 with trainer 8 (7 ≤ 8). Player 9 cannot be matched since no remaining trainer has capacity ≥ 9.

Example 2 — All Players Match

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

› Output: 1

💡 Note: Only one trainer available, so we can match at most one player. All players have ability 1 ≤ 10, but each trainer can only match with one player.

Example 3 — No Matches Possible

$ Input: players = [10,20,30], trainers = [5,6,7]

› Output: 0

💡 Note: No player can be matched because every player's ability exceeds every trainer's capacity.

Constraints

1 ≤ players.length, trainers.length ≤ 10⁵
1 ≤ players[i], trainers[j] ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

Players with abilities and trainers with capacities

Matching Rule

Player ability ≤ trainer capacity, 1-to-1 matching

Output

Maximum number of valid matches possible

Key Takeaway

🎯 Key Insight: Sort both arrays and greedily match each player with the weakest suitable trainer

Asked in

G Google 25 a Amazon 18 M Microsoft 15 f Meta 12

The key insight is that greedy matching works optimally when both arrays are sorted. Sort both players and trainers, then use two pointers to match each player with the weakest available trainer that can handle them. Best approach is Greedy with Sorting: Time: O(n log n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Greedy with Sorting	O(n log n + m log m)	O(1)	Sort both arrays and greedily match from weakest to strongest
Brute Force - Try All Combinations	O(2^(n×m))	O(n×m)	Generate all possible matchings and find the maximum valid ones

Greedy with Sorting — Algorithm Steps

Sort players array in ascending order
Sort trainers array in ascending order
Use two pointers to match players greedily
For each player, find the weakest suitable trainer

Visualization

Tap to expand

Step-by-Step Walkthrough

Sort Arrays

Sort both players and trainers in ascending order

Two Pointers

Match each player with weakest suitable trainer

Optimal Result

Greedy approach gives maximum matches

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int compare(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}

int* parseArray(char* s, int* size) {
    int* arr = malloc(1000 * sizeof(int));
    *size = 0;
    char* token = strtok(s + 1, ",]");
    while (token != NULL) {
        arr[(*size)++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    return arr;
}

int solution(int* players, int playersSize, int* trainers, int trainersSize) {
    // Sort both arrays
    qsort(players, playersSize, sizeof(int), compare);
    qsort(trainers, trainersSize, sizeof(int), compare);
    
    int matches = 0;
    int trainerIdx = 0;
    
    // Greedily match each player with the weakest suitable trainer
    for (int i = 0; i < playersSize; i++) {
        int player = players[i];
        
        // Find the first available trainer who can handle this player
        while (trainerIdx < trainersSize && trainers[trainerIdx] < player) {
            trainerIdx++;
        }
        
        // If we found a suitable trainer, make the match
        if (trainerIdx < trainersSize) {
            matches++;
            trainerIdx++; // This trainer is now used
        }
    }
    
    return matches;
}

int main() {
    char line1[10000], line2[10000];
    fgets(line1, sizeof(line1), stdin);
    fgets(line2, sizeof(line2), stdin);
    
    int playersSize, trainersSize;
    int* players = parseArray(line1, &playersSize);
    int* trainers = parseArray(line2, &trainersSize);
    
    int result = solution(players, playersSize, trainers, trainersSize);
    printf("%d\n", result);
    
    free(players);
    free(trainers);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n + m log m)

Sorting players takes O(n log n) and trainers takes O(m log m), then O(n + m) for matching

⚡ Linearithmic

Space Complexity

O(1)

Only using constant extra space for pointers and counters

✓ Linear Space

32.5K Views

Medium Frequency

~15 min Avg. Time

847 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Greedy with Sorting — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler