We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Maximum Matching of Players With Trainers

Difficulty: Medium

Problem Description

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. The ith player can match with the jth trainer if the player's ability is less than or equal to the trainer's training capacity. Additionally, the ith player can be matched with at most one trainer, and the jth trainer can be matched with at most one player. Return the maximum number of matchings between players and trainers that satisfy these conditions.

Key Insights

  • Players can only be matched with trainers if the player's ability is less than or equal to the trainer's training capacity.
  • Each player and trainer can only participate in one match.
  • Sorting both players and trainers allows for a more efficient matching process.
  • A two-pointer technique can be utilized to traverse both sorted lists and find valid matches.

Space and Time Complexity

Time Complexity: O(n log n + m log m), where n is the number of players and m is the number of trainers (due to sorting). Space Complexity: O(1), since we are using pointers and not requiring additional data structures that grow with input size.

Solution

To solve the problem, we can use the following approach:

  1. Sort both the players and trainers arrays.
  2. Use two pointers to iterate through both arrays:
    • One pointer for players and another for trainers.
    • For each player, check if they can be matched with the current trainer.
    • If they can be matched, increment the count of matches and move both pointers forward.
    • If they cannot be matched (player's ability is greater than the trainer's capacity), only move the trainer's pointer forward to find a more suitable trainer.
  3. Continue this until we have processed all players or trainers.

This greedy approach ensures that we maximize the number of matches while respecting the constraints given.

Code Solutions

def maxPlayers(players, trainers):
    players.sort()
    trainers.sort()
    
    player_pointer = 0
    trainer_pointer = 0
    matches = 0
    
    while player_pointer < len(players) and trainer_pointer < len(trainers):
        if players[player_pointer] <= trainers[trainer_pointer]:  # Match found
            matches += 1
            player_pointer += 1
            trainer_pointer += 1
        else:  # No match, move to next trainer
            trainer_pointer += 1
            
    return matches
← Back to All Questions