#2410

Medium

auto_awesomeTwo-pointer scanning with invariant tracking

LeetCode Problem Workspace

Maximum Matching of Players With Trainers

Maximize the number of valid player-trainer matchings using two-pointer scanning and careful sorting strategy.

Problem Statement

You are given two integer arrays, players and trainers. Each players[i] represents the ability of the ith player, and each trainers[j] represents the training capacity of the jth trainer. A player can only be matched with a trainer whose capacity is greater than or equal to the player's ability. Each player and trainer can participate in at most one matching.

Return the maximum number of player-trainer pairs that satisfy the matching condition. Use sorting and two-pointer scanning to efficiently pair players with trainers while maintaining the invariant that each match uses the smallest suitable trainer available.

Examples

Example 1

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

Output: 2

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

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 <= 105
1 <= players[i], trainers[j] <= 109

Solution Approach

Sort Both Arrays

Sort players and trainers in ascending order to allow efficient scanning and pairing. Sorting ensures that the smallest available trainer can be matched with the smallest player who needs training.

Two-Pointer Matching

Use one pointer for players and one for trainers. If the current player's ability is less than or equal to the current trainer's capacity, count a match and move both pointers. Otherwise, move the trainer pointer to find a sufficient capacity.

Invariant Tracking

Maintain the invariant that every matched player uses the minimal capable trainer. This ensures no better pairing is missed, achieving the maximum possible matchings while keeping the algorithm linear after sorting.

Complexity Analysis

Metric	Value
Time	O(m \log m + n \log n)
Space	O(\log m + \log n)

Sorting both arrays takes O(m log m + n log n) time, and the two-pointer scan is O(m + n) time. Space complexity is O(log m + log n) due to recursion in sorting.

What Interviewers Usually Probe

Pay attention to array ordering; an unsorted approach may miss optimal matches.
Demonstrate correct two-pointer increments and match counting.
Explain why using the smallest suitable trainer ensures maximum matches.

Common Pitfalls or Variants

Common pitfalls

Not sorting the arrays can lead to suboptimal matchings.
Incrementing only one pointer incorrectly can skip valid pairings.
Failing to track which players or trainers are already matched.

Follow-up variants

Consider a variant where each trainer can train multiple players, requiring adjusted pointer logic.
A version where players have minimum and maximum acceptable trainer capacities changes the greedy invariant.
Randomly shuffled arrays with large input sizes test the efficiency of sorting plus two-pointer scan.

FAQ

What is the best approach for Maximum Matching of Players With Trainers?

Sort both players and trainers arrays, then apply a two-pointer greedy scan to match each player with the smallest available trainer who can train them.

Why does sorting matter in this problem?

Sorting ensures that we always consider the minimal trainer for each player first, preventing suboptimal matches and maximizing the total pairings.

Can a trainer be matched with multiple players?

No, each trainer can be matched with at most one player, which is why careful pointer tracking is necessary.

What is the time complexity of this solution?

The total time complexity is O(m log m + n log n) due to sorting, with the two-pointer scan adding O(m + n) linear time.

How does the two-pointer scanning pattern help here?

It ensures we efficiently pair each player with the next eligible trainer, maintaining the invariant that every match uses the minimal suitable trainer, which guarantees the maximum number of matches.

terminal

Solution

Solution 1: Greedy + Two Pointers

According to the problem description, each athlete should be matched with the trainer whose ability value is as close as possible. Therefore, we can sort the ability values of both athletes and trainers, and then use the two-pointer method for matching.

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def matchPlayersAndTrainers(self, players: List[int], trainers: List[int]) -> int:
        players.sort()
        trainers.sort()
        j, n = 0, len(trainers)
        for i, p in enumerate(players):
            while j < n and trainers[j] < p:
                j += 1
            if j == n:
                return i
            j += 1
        return len(players)

Continue Practicing

#2406 divide intervals into minimum number of groups #2576 find the maximum number of marked indices #2234 maximum total beauty of the gardens