# Best Team With No Conflicts
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/best-team-with-no-conflicts)
Canonical: https://scaleengineer.com/dsa/problems/best-team-with-no-conflicts
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
**Companies:** [Morgan Stanley](https://scaleengineer.com/companies/morgan-stanley)
---
## Problem
You are the manager of a basketball team. For the upcoming tournament, you want to choose the team with the highest overall score. The score of the team is the **sum** of scores of all the players in the team.

However, the basketball team is not allowed to have **conflicts**. A **conflict** exists if a younger player has a **strictly higher** score than an older player. A conflict does **not** occur between players of the same age.

Given two lists, `scores` and `ages`, where each `scores[i]` and `ages[i]` represents the score and age of the `ith` player, respectively, return _the highest overall score of all possible basketball teams_.

**Example 1:**

**Input:** scores = [1,3,5,10,15], ages = [1,2,3,4,5]
**Output:** 34
**Explanation:** You can choose all the players.

**Example 2:**

**Input:** scores = [4,5,6,5], ages = [2,1,2,1]
**Output:** 16
**Explanation:** It is best to choose the last 3 players. Notice that you are allowed to choose multiple people of the same age.

**Example 3:**

**Input:** scores = [1,2,3,5], ages = [8,9,10,1]
**Output:** 6
**Explanation:** It is best to choose the first 3 players. 

**Constraints:**

* `1 <= scores.length, ages.length <= 1000`
* `scores.length == ages.length`
* `1 <= scores[i] <= 106`
* `1 <= ages[i] <= 1000`

# Approaches
## Brute Force with Recursion
This approach attempts to solve the problem by exploring every possible subset of players. For each subset, it checks if it forms a valid team (i.e., has no conflicts). If the team is valid, its total score is calculated. The algorithm keeps track of the maximum score found across all valid teams. This method guarantees finding the optimal solution by sheer force of checking all possibilities, but it is computationally very expensive.
**Time:** O(2^N * N). There are 2^N possible subsets of players. For each subset, we perform a validity check which can take up to O(N^2) in a naive implementation, or O(N) per inclusion step as shown in the code. This results in an overall exponential time complexity. · **Space:** O(N), where N is the number of players. This space is used for the recursion stack and to store the players in the current team being built.
**Pros:** Simple to understand and implement the logic.; Guaranteed to find the correct answer for small inputs.
**Cons:** Extremely inefficient due to its exponential time complexity.; Will result in a 'Time Limit Exceeded' error on platforms like LeetCode for the given constraints.
### Explanation
The brute-force solution can be implemented using recursion and backtracking. We define a helper function that builds a team by making a decision for each player one by one: either include them in the team or not.

We start with an empty team and at index 0. For each player, we first recurse without including them. Then, we check if including them would violate the no-conflict rule with the players already in our `currentTeam`. If it's a valid addition, we add them and recurse again. This process explores the entire decision tree of team compositions. A global variable tracks the maximum score found. When the recursion reaches the end of the player list, it means we have formed one possible team, and we update our global maximum if its score is higher.

```java
class Solution {
    int maxScore = 0;

    public int bestTeamScore(int[] scores, int[] ages) {
        int n = scores.length;
        Player[] players = new Player[n];
        for (int i = 0; i < n; i++) {
            players[i] = new Player(ages[i], scores[i]);
        }
        
        findMax(players, 0, new java.util.ArrayList<>());
        return maxScore;
    }

    private void findMax(Player[] players, int index, java.util.List<Player> currentTeam) {
        if (index == players.length) {
            int currentScore = 0;
            for (Player p : currentTeam) {
                currentScore += p.score;
            }
            maxScore = Math.max(maxScore, currentScore);
            return;
        }

        // Option 1: Exclude the current player
        findMax(players, index + 1, currentTeam);

        // Option 2: Include the current player, if valid
        if (isCompatible(players[index], currentTeam)) {
            currentTeam.add(players[index]);
            findMax(players, index + 1, currentTeam);
            currentTeam.remove(currentTeam.size() - 1); // backtrack
        }
    }

    private boolean isCompatible(Player newPlayer, java.util.List<Player> team) {
        for (Player teamMember : team) {
            if (newPlayer.age < teamMember.age && newPlayer.score > teamMember.score) {
                return false;
            }
            if (newPlayer.age > teamMember.age && newPlayer.score < teamMember.score) {
                return false;
            }
        }
        return true;
    }

    class Player {
        int age;
        int score;
        Player(int age, int score) {
            this.age = age;
            this.score = score;
        }
    }
}
```
### Algorithm
*   Define a recursive function, say `findMax(index, currentTeam)`, to explore all team compositions.
*   The `index` parameter tracks the current player being considered, and `currentTeam` is a list of players chosen so far.
*   **Base Case**: When `index` reaches the total number of players, calculate the score of `currentTeam`. Update a global `maxScore` if the current team's score is higher.
*   **Recursive Step**: For each player at `index`, there are two choices:
    1.  **Exclude**: Don't add the player to the team. Recurse for the next player: `findMax(index + 1, currentTeam)`.
    2.  **Include**: Check if adding `player[index]` to `currentTeam` is valid. A new player is compatible if they don't create a conflict with any existing member of `currentTeam`. A conflict occurs if `(newPlayer.age < member.age && newPlayer.score > member.score)` or `(newPlayer.age > member.age && newPlayer.score < member.score)`. If compatible, add the player and recurse: `findMax(index + 1, newTeam)`. After the recursive call returns, backtrack by removing the player to explore other possibilities.

## Dynamic Programming
A more efficient approach uses dynamic programming. The key insight is to transform the problem into a variation of the Longest Increasing Subsequence (LIS) problem. By sorting the players first by age and then by score, the conflict condition simplifies significantly. A conflict exists if a younger player has a strictly higher score than an older one. After sorting, if we pick a subsequence of players, their ages will be non-decreasing. The no-conflict rule then just requires that their scores also be non-decreasing. The problem becomes finding a subsequence with non-decreasing scores that has the maximum possible sum of scores.
**Time:** O(N^2). Sorting the players takes O(N log N). The main part of the algorithm involves two nested loops to fill the DP table, which takes O(N^2) time. Thus, the overall complexity is dominated by the DP calculation. · **Space:** O(N) to store the player objects and the DP array.
**Pros:** Significantly more efficient than the brute-force approach.; Correctly solves the problem within the time limits for the given constraints.
**Cons:** The O(N^2) time complexity might be slow for very large N, although it passes for the given constraints.
### Explanation
First, we create pairs of `(age, score)` and sort them. The primary sort key is `age`, and for players with the same age, we use `score` as the secondary sort key. This sorting is crucial.

Let `dp[i]` be the maximum score of a valid team where player `i` (from the sorted list) is the last player added. To compute `dp[i]`, we can either form a team with just player `i` (score = `players[i].score`), or we can add player `i` to an existing valid team that ends with some player `j` (where `j < i`).

Because of our sorting strategy, for any `j < i`, `players[j].age <= players[i].age`. The no-conflict rule is only violated if `players[j].age < players[i].age` and `players[j].score > players[i].score`. However, if we only consider adding player `i` to teams ending with `j` where `players[j].score <= players[i].score`, we can never violate the rule. If `players[j].age == players[i].age`, our secondary sort on score ensures `players[j].score <= players[i].score`, and there's no conflict anyway.

Thus, the recurrence relation is: `dp[i] = players[i].score + max({0} U {dp[j] for all j < i where players[j].score <= players[i].score})`.
The final answer is the maximum value in the `dp` array.

```java
import java.util.Arrays;

class Solution {
    class Player {
        int age, score;
        Player(int age, int score) { this.age = age; this.score = score; }
    }

    public int bestTeamScore(int[] scores, int[] ages) {
        int n = scores.length;
        Player[] players = new Player[n];
        for (int i = 0; i < n; i++) {
            players[i] = new Player(ages[i], scores[i]);
        }

        Arrays.sort(players, (a, b) -> {
            if (a.age != b.age) {
                return a.age - b.age;
            } else {
                return a.score - b.score;
            }
        });

        int[] dp = new int[n];
        int maxTotalScore = 0;

        for (int i = 0; i < n; i++) {
            dp[i] = players[i].score;
            for (int j = 0; j < i; j++) {
                if (players[j].score <= players[i].score) {
                    dp[i] = Math.max(dp[i], players[i].score + dp[j]);
                }
            }
            maxTotalScore = Math.max(maxTotalScore, dp[i]);
        }

        return maxTotalScore;
    }
}
```
### Algorithm
*   Create a list of `Player` objects, each containing an `age` and a `score`.
*   Sort this list of players. The primary sorting key is `age` (ascending), and the secondary sorting key is `score` (ascending).
*   Initialize a DP array, `dp`, of size `n`. `dp[i]` will store the maximum score of a valid team that includes player `i` (from the sorted list).
*   Iterate from `i = 0` to `n-1`:
    *   Initialize `dp[i]` with the score of player `i`, representing a team with only that player.
    *   Iterate from `j = 0` to `i-1`:
        *   Check if player `i` can be added to a team ending with player `j`. Due to the sorting, this condition simplifies to `players[j].score <= players[i].score`.
        *   If the condition holds, update `dp[i] = max(dp[i], players[i].score + dp[j])`.
*   The final answer is the maximum value found in the `dp` array.

## Optimized DP with Fenwick Tree
The O(N^2) DP solution can be further optimized. The bottleneck is the inner loop, which performs a linear scan to find the maximum `dp[j]` among all preceding players `j` that satisfy the score condition. This subproblem of finding a maximum value in a range can be solved more efficiently using a suitable data structure, such as a Fenwick Tree or a Segment Tree. This optimization reduces the time complexity from quadratic to nearly linearithmic.
**Time:** O(N log N + N log S), where S is the maximum score. Sorting takes O(N log N). The main loop runs N times, and each iteration involves a query and an update on the Fenwick Tree, both of which take O(log S) time. · **Space:** O(N + S), where N is the number of players and S is the maximum possible score. O(N) is for storing player data, and O(S) is for the Fenwick Tree.
**Pros:** This is the most efficient approach in terms of time complexity.; It handles the given constraints very effectively.
**Cons:** More complex to implement due to the need for a Fenwick Tree or a similar data structure.; Space complexity depends on the maximum score value, which can be large (up to 10^6), potentially consuming significant memory.
### Explanation
We maintain the same DP logic but accelerate the query for `max({dp[j]})`. After sorting players by age and then score, we process them one by one. We use a Fenwick Tree (BIT) to keep track of the maximum team scores achieved so far, indexed by the player's score.

For each player `i` with score `s_i`, we need to find the maximum score of a valid team composed of players from `0` to `i-1` whose scores are less than or equal to `s_i`. This is exactly what a range maximum query on our BIT can provide. `bit.query(s_i)` will give us the maximum team score ending with a player whose score is at most `s_i`.

Let this value be `max_prev_score`. The new maximum score for a team including player `i` is `s_i + max_prev_score`. We then update the BIT at index `s_i` with this new, potentially higher, team score. The overall maximum score seen during this process is the answer.

```java
import java.util.Arrays;

class Solution {
    class Player {
        int age, score;
        Player(int age, int score) { this.age = age; this.score = score; }
    }

    class FenwickTree {
        private int[] tree;
        
        public FenwickTree(int size) {
            tree = new int[size + 1];
        }

        public void update(int index, int value) {
            index++; // 1-based index
            while (index < tree.length) {
                tree[index] = Math.max(tree[index], value);
                index += index & (-index);
            }
        }

        public int query(int index) {
            index++; // 1-based index
            int max = 0;
            while (index > 0) {
                max = Math.max(max, tree[index]);
                index -= index & (-index);
            }
            return max;
        }
    }

    public int bestTeamScore(int[] scores, int[] ages) {
        int n = scores.length;
        Player[] players = new Player[n];
        int maxScoreVal = 0;
        for (int i = 0; i < n; i++) {
            players[i] = new Player(ages[i], scores[i]);
            maxScoreVal = Math.max(maxScoreVal, scores[i]);
        }

        Arrays.sort(players, (a, b) -> {
            if (a.age != b.age) return a.age - b.age;
            return a.score - b.score;
        });

        FenwickTree bit = new FenwickTree(maxScoreVal);
        int maxTotalScore = 0;

        for (Player player : players) {
            int maxPrevScore = bit.query(player.score);
            int currentTotalScore = player.score + maxPrevScore;
            bit.update(player.score, currentTotalScore);
            maxTotalScore = Math.max(maxTotalScore, currentTotalScore);
        }

        return maxTotalScore;
    }
}
```
### Algorithm
*   Create and sort the `Player` objects by age, then score, as in the previous DP approach.
*   Determine the maximum possible score `maxS` from the input to set the size of our data structure.
*   Initialize a Fenwick Tree (also known as a Binary Indexed Tree or BIT) of size `maxS + 1`. This BIT will be used to find the maximum team score for players up to a certain score.
*   Initialize an overall `maxTotalScore` to 0.
*   Iterate through the sorted `players` array:
    *   For the current `player` with score `s`:
        *   Query the BIT for the maximum value in the range `[0, s]`. This gives the maximum score of a valid team we can extend: `maxPrevScore = bit.query(s)`.
        *   Calculate the new team score including the current player: `currentTotalScore = player.score + maxPrevScore`.
        *   Update the BIT at index `s` with this new score: `bit.update(s, currentTotalScore)`. Note that the update operation should store the maximum, not sum.
        *   Update the overall `maxTotalScore = max(maxTotalScore, currentTotalScore)`.
*   The final answer is `maxTotalScore`.

# Solutions
### Java

```java
class Solution {
public
  int bestTeamScore(int[] scores, int[] ages) {
    int n = ages.length;
    int[][] arr = new int[n][2];
    for (int i = 0; i < n; ++i) {
      arr[i] = new int[]{scores[i], ages[i]};
    }
    Arrays.sort(arr, (a, b)->a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);
    int[] f = new int[n];
    int ans = 0;
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < i; ++j) {
        if (arr[i][1] >= arr[j][1]) {
          f[i] = Math.max(f[i], f[j]);
        }
      }
      f[i] += arr[i][0];
      ans = Math.max(ans, f[i]);
    }
    return ans;
  }
}

```

### JavaScript

```javascript
/** * @param {number[]} scores * @param {number[]} ages * @return {number} */ var bestTeamScore =
  function (scores, ages) {
    const arr = ages.map((age, i) => [age, scores[i]]);
    arr.sort((a, b) => (a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]));
    const n = arr.length;
    const f = new Array(n).fill(0);
    for (let i = 0; i < n; ++i) {
      for (let j = 0; j < i; ++j) {
        if (arr[i][1] >= arr[j][1]) {
          f[i] = Math.max(f[i], f[j]);
        }
      }
      f[i] += arr[i][1];
    }
    return Math.max(...f);
  };

```

### CPP

```cpp
class Solution {
public:
  int bestTeamScore(vector<int> &scores, vector<int> &ages) {
    int n = ages.size();
    vector<pair<int, int>> arr(n);
    for (int i = 0; i < n; ++i) {
      arr[i] = {scores[i], ages[i]};
    }
    sort(arr.begin(), arr.end());
    vector<int> f(n);
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < i; ++j) {
        if (arr[i].second >= arr[j].second) {
          f[i] = max(f[i], f[j]);
        }
      }
      f[i] += arr[i].first;
    }
    return *max_element(f.begin(), f.end());
  }
};

```

### Python

```python
class Solution:
    def bestTeamScore(self, scores: List[int], ages: List[int]) -> int: arr = sorted(zip(scores, ages)) n = len(arr) f = [0] * n for i, (score, age) in enumerate(arr): for j in range(i): if age >= arr[j][1]: f[i] = max(f[i], f[j]) f[i] += score return max(f)

```