Maximum Matching of Players With Trainers — LeetCode 2410 Python Solution

The problem

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

Example

Input

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

Output

2

Explanation

One of the ways we can form two matchings is as follows:

Python solution

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)

Complexity

Pattern: Two Pointers

Use the order already in the input to discard half the search space at every step. LeetCode 2410. Maximum Matching of Players With Trainers is filed here because LeetCode tags it Two Pointers, which is the vocabulary this hub collects.

The two pointers guide has the Python template for the pattern and the 201 LeetCode problems that use it.

Related problems