< Back





2410. Maximum Matching of Players With Trainers

Similar to our greedy children with cookies problem, we have players that need trainers, it's a 1:1
matching. Once a pair is created, we can't reuse those elements. The simplest solution involves
pairing the lowest skilled players with the lowest skilled trainers first. We sort both inputs and
iterate across both lists using two pointers. If a match is made between a player and a trainer,
we increment the result and move both pointers. If a match can't be made, we move the trainer pointer
to the right. We continue this process until we've iterated through all the players.

The solution is as follows:


  class Solution:
      def matchPlayersAndTrainers(self, players: List[int], trainers: List[int]) -> int:
          players.sort()
          trainers.sort()
          m, n = len(players), len(trainers)
          ans = i = j = 0

          while i < m and j < n:
              if players[i] <= trainers[j]:
                  i += 1
                  ans += 1

              j += 1

          return ans


_ Time Complexity:

  O(n * log(n) + m * log(m)) - We sort both lists.

_ Space Complexity:

  O(n + m) - Sorting in Python requires n space.