Best Team With No Conflicts

Medium
1620.

Best Team With No Conflicts

Best Team With No Conflicts is a medium coding problem on arrays, dynamic programming and sorting, asked in Amazon and Google interviews.

A coach is picking a team for a CodeKairo tournament. Player i has a rating scores[i] and an age ages[i]; the team's score is the sum of its players' scores.

The team must have no conflict: a conflict happens when a younger player has a strictly higher score than an older player. Two players of the same age never conflict.

Return the highest team score the coach can reach.

Example 1

Input
scores = [1,3,5,10,15], ages = [1,2,3,4,5]
Output
34
Explanation
Scores rise with age, so everyone can play together.

Example 2

Input
scores = [4,5,6,5], ages = [2,1,2,1]
Output
16
Explanation
Take the last three players: the two 1-year-olds score 5 and 5, and the 2-year-old scores 6. The first player (age 2, score 4) would conflict with the younger players scoring 5.

Example 3

Input
scores = [1,2,3,5], ages = [8,9,10,1]
Output
6
Explanation
The youngest player (score 5) conflicts with every older player, so take the first three: 1 + 2 + 3 = 6.

Constraints

  • 1 <= scores.length, ages.length <= 1000
  • scores.length == ages.length
  • 1 <= scores[i] <= 10^6
  • 1 <= ages[i] <= 1000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} scores
 * @param {number[]} ages
 * @return {number}
 */
var bestTeamScore = function(scores, ages) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Best Team With No Conflicts — Solution in Python, Java & C++

Best Team With No Conflicts solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Best Team With No Conflicts is a medium coding problem on arrays, dynamic programming and sorting, asked in Amazon and Google interviews.

Problem statement

A coach is picking a team for a CodeKairo tournament. Player i has a rating scores[i] and an age ages[i]; the team's score is the sum of its players' scores.

The team must have no conflict: a conflict happens when a younger player has a strictly higher score than an older player. Two players of the same age never conflict.

Return the highest team score the coach can reach.

Example 1

Input: scores = [1,3,5,10,15], ages = [1,2,3,4,5]
Output: 34
Explanation: Scores rise with age, so everyone can play together.

Example 2

Input: scores = [4,5,6,5], ages = [2,1,2,1]
Output: 16
Explanation: Take the last three players: the two 1-year-olds score 5 and 5, and the 2-year-old scores 6. The first player (age 2, score 4) would conflict with the younger players scoring 5.

Example 3

Input: scores = [1,2,3,5], ages = [8,9,10,1]
Output: 6
Explanation: The youngest player (score 5) conflicts with every older player, so take the first three: 1 + 2 + 3 = 6.

Constraints

  • 1 <= scores.length, ages.length <= 1000
  • scores.length == ages.length
  • 1 <= scores[i] <= 10^6
  • 1 <= ages[i] <= 1000

Hints for Best Team With No Conflicts

  1. Hint 1

    Sort the players by age, breaking ties by score. In that order, when is a set of players conflict-free?

  2. Hint 2

    After sorting, a team is valid exactly when its scores never go down from one chosen player to the next.

  3. Hint 3

    So the answer is a maximum-sum non-decreasing subsequence of the sorted scores: dp[i] = scores[i] + max(dp[j]) over earlier j with scores[j] <= scores[i].

How to solve Best Team With No Conflicts

Sorting by (age, score) turns the pairwise conflict rule into a chain condition: a team is valid if and only if its scores are non-decreasing in that order. The best team is then a maximum-sum non-decreasing subsequence.

Approach

  1. Sort the players by age, and by score among players of the same age.
  2. For each player i in that order, set dp[i] to its score plus the largest dp[j] over earlier players j whose score is at most scores[i] (or plus 0 if none).
  3. Return the largest dp[i].

Why it works

Two chosen players in sorted order either share an age (no conflict, and the tie-break puts the lower score first) or the earlier one is younger, in which case a conflict means exactly that its score is higher. So a set is conflict-free iff its scores never decrease along the sorted order, and the DP enumerates every such chain ending at each player.

Complexity

  • Time — O(n^2)
  • Space — O(n)

Pitfalls

  • Ties in age must be broken by score: sorting by age alone can put a higher score first and wrongly forbid two same-aged players together.
  • The comparison is <=, not < — equal scores never conflict.
  • The answer is the maximum over all dp[i], not dp[n - 1].

Reference solution

Python

from typing import List

def bestTeamScore(scores: List[int], ages: List[int]) -> int:
    players = sorted(zip(ages, scores))
    dp = []
    best = 0
    for i, (_, s) in enumerate(players):
        top = 0
        for j in range(i):
            if players[j][1] <= s and dp[j] > top:
                top = dp[j]
        dp.append(top + s)
        best = max(best, top + s)
    return best

Java

public static int bestTeamScore(int[] scores, int[] ages) {
    int n = scores.length;
    Integer[] order = new Integer[n];
    for (int i = 0; i < n; i++) order[i] = i;
    Arrays.sort(order, (a, b) -> ages[a] != ages[b] ? ages[a] - ages[b] : scores[a] - scores[b]);
    int[] dp = new int[n];
    int best = 0;
    for (int i = 0; i < n; i++) {
        int s = scores[order[i]], top = 0;
        for (int j = 0; j < i; j++) if (scores[order[j]] <= s && dp[j] > top) top = dp[j];
        dp[i] = top + s;
        best = Math.max(best, dp[i]);
    }
    return best;
}

C++

int bestTeamScore(vector<int>& scores, vector<int>& ages) {
    int n = scores.size();
    vector<pair<int, int>> players(n);
    for (int i = 0; i < n; i++) players[i] = {ages[i], scores[i]};
    sort(players.begin(), players.end());
    vector<int> dp(n, 0);
    int best = 0;
    for (int i = 0; i < n; i++) {
        int s = players[i].second, top = 0;
        for (int j = 0; j < i; j++) if (players[j].second <= s && dp[j] > top) top = dp[j];
        dp[i] = top + s;
        best = max(best, dp[i]);
    }
    return best;
}

JavaScript

var bestTeamScore = function(scores, ages) {
    var n = scores.length, order = [];
    for (var i = 0; i < n; i++) order.push(i);
    order.sort(function(a, b) { return ages[a] !== ages[b] ? ages[a] - ages[b] : scores[a] - scores[b]; });
    var dp = [], best = 0;
    for (var i = 0; i < n; i++) {
        var s = scores[order[i]], top = 0;
        for (var j = 0; j < i; j++) if (scores[order[j]] <= s && dp[j] > top) top = dp[j];
        dp.push(top + s);
        if (top + s > best) best = top + s;
    }
    return best;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming