Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Match the least demanding unmatched player with the weakest trainer capable of handling them. A trainer too weak for that player cannot serve any remaining player, while spending a stronger trainer unnecessarily could block a later match.

Approach

Sort both lists. Scan trainers in ascending order with a pointer to the first unmatched player. Skip trainers below that player's ability; otherwise record a match and advance the player pointer. Stop when every player is matched or trainers are exhausted. Return the match count. Each successful greedy choice can replace the corresponding choice in an optimal matching without reducing the number of matches.

class Solution:
    def matchPlayersAndTrainers(self, players: List[int], trainers: List[int]) -> int:
        players.sort()
        trainers.sort()
        p = len(players)
        t = len(trainers)
        i = 0
        res = 0

        for j in range(t):
            if trainers[j] >= players[i]:
                res += 1
                i += 1
                if i == p:
                    break

        return res

Complexity analysis

Let p = players.length and t = trainers.length. Time: O(p log p + t log t) for sorting plus a linear greedy scan. Auxiliary space: up to O(p + t) for sorting workspace.