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

Best Team With No Conflicts

Number: 1748

Difficulty: Medium

Paid? No

Companies: Morgan Stanley

Problem Description

Given two lists, scores and ages, where scores[i] and ages[i] represent the score and age of the iᵗʰ player, select a subset of players (team) such that no conflicts occur. A conflict means that a younger player has a strictly higher score than an older player. The goal is to choose the team that maximizes the overall score (the sum of the chosen players' scores).

Key Insights

  • Sort players primarily by age and secondarily by score. This ensures that when traversing the sorted list, older players (or those with equal age) come later.
  • After sorting, the problem reduces to finding a subset (not necessarily contiguous) with non-decreasing scores.
  • Use dynamic programming: for each player, consider the best team you can form ending with that player by adding the player’s score to the maximum team score from compatible previous players.
  • The final answer is the maximum team score found among all players.

Space and Time Complexity

Time Complexity: O(n²)
Space Complexity: O(n)

Solution

The solution begins by pairing each player's age and score together and sorting the list so that players are sorted by age and, in case of a tie in age, by score. This ordering guarantees that if a player comes later in the sorted list, their age is greater (or equal) and picking them will not create conflicts if their score is also not lower than the player's score before them.

We use a dynamic programming array, dp, where dp[i] represents the maximum overall score of a valid team ending with the iᵗʰ player in the sorted list. For each player i, we check all previous players j (j < i) and update dp[i] if the score of player j is less than or equal to the score of player i. Finally, the answer is the maximum value in the dp array.

Code Solutions

# Pair players as (age, score) and sort them 
def bestTeamScore(scores, ages):
    # Create pairs of (age, score) for each player
    players = list(zip(ages, scores))
    # Sort players by age first, and by score if ages are equal
    players.sort(key=lambda x: (x[0], x[1]))
    
    n = len(players)
    dp = [0] * n  # dp[i] will hold the max team score ending with i-th player
    
    # Iterate over each player in the sorted order
    for i in range(n):
        age_i, score_i = players[i]
        dp[i] = score_i  # Team with only the current player
        # Check previous players to see if they can be added without conflict
        for j in range(i):
            age_j, score_j = players[j]
            if score_j <= score_i:  # Valid if no conflict in scores
                dp[i] = max(dp[i], dp[j] + score_i)
                
    # The answer is the maximum team score possible
    return max(dp)

# Example usage:
print(bestTeamScore([1,3,5,10,15], [1,2,3,4,5]))  # Output: 34
← Back to All Questions