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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Matching of Players With Trainers

Number: 2497

Difficulty: Medium

Paid? No

Companies: Amazon

Problem Description

You are given two arrays: players and trainers. Each player has an ability, and each trainer has a training capacity. A player can be matched with a trainer if the player's ability is less than or equal to the trainer's capacity. Each player and trainer can participate in at most one match. The goal is to determine the maximum number of matchings possible between players and trainers.

Key Insights

  • Sort both the players and trainers arrays.
  • Use a two-pointer technique to traverse both arrays simultaneously.
  • When a player's ability is less than or equal to a trainer's capacity, count a match and move both pointers forward.
  • If the current trainer's capacity is insufficient for the current player, move the trainer pointer to check the next trainer.

Space and Time Complexity

Time Complexity: O(n log n + m log m), where n and m are the lengths of the players and trainers arrays respectively (due to sorting). Space Complexity: O(1) if sorting is done in-place.

Solution

The solution leverages a greedy approach by sorting both arrays so that the least capable player is paired with the least capable trainer that can train them. Two pointers iterate over the arrays:

  • If the current player's ability is <= current trainer's capacity, a match is made.
  • Both pointers are then incremented.
  • Otherwise, only the trainer pointer is moved forward to find a suitable trainer. This strategy ensures that the matching is optimized, leading to the maximum count of possible matchings.

Code Solutions

def max_matching(players, trainers):
    # Sort the players and trainers to pair the smallest capable ones first.
    players.sort()
    trainers.sort()
    
    player_index = 0  # Pointer for players array
    trainer_index = 0  # Pointer for trainers array
    match_count = 0   # Count of successful matchings
    
    # Traverse both arrays until one is exhausted
    while player_index < len(players) and trainer_index < len(trainers):
        # If the player's ability is less than or equal to the trainer's capacity, match them
        if players[player_index] <= trainers[trainer_index]:
            match_count += 1
            player_index += 1
            trainer_index += 1
        else:
            # Trainer cannot train the current player, try the next trainer
            trainer_index += 1
    
    return match_count

# Example usage:
players = [4, 7, 9]
trainers = [8, 2, 5, 8]
print(max_matching(players, trainers))  # Expected Output: 2
← Back to All Questions