1626. Best Team with no Conflicts - Explanation

Prerequisites

Before attempting this problem, you should be comfortable with:

Sorting - Used to order players by score/age to simplify conflict detection
Dynamic Programming (Memoization) - Required for the top-down recursive approach with caching
Dynamic Programming (Tabulation) - Used in the bottom-up iterative approach
Segment Trees - Optional for the O(n log n) optimization to efficiently query maximum values

1. Dynamic Programming (Top-Down)

Intuition

A conflict happens when a younger player has a higher score than an older player. To handle this cleanly, we sort players by score (and by age as a tiebreaker). After sorting, as we iterate through players in order, we only need to check if a new player's age is compatible with the last player we picked. If the current player has an equal or higher age than the last picked player, there is no conflict since the scores are already in non-decreasing order. We use recursion with memoization to explore all valid team combinations and find the maximum total score.

Algorithm

Create pairs of (score, age) for each player and sort them by score, then by age.
Use a recursive function dfs(i, j) where i is the current player index and j is the index of the last picked player.
At each step, we can either skip the current player or include them if their age is greater than or equal to the last picked player's age.
Memoize results using a dictionary or 2D array to avoid recomputation.
Return the maximum score achievable starting from index 0 with no prior selection.

class Solution:
    def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:
        pairs = [[scores[i], ages[i]] for i in range(len(scores))]
        pairs.sort()
        dp = {}

        def dfs(i, j):
            if i == len(pairs):
                return 0
            if (i, j) in dp:
                return dp[(i, j)]

            mScore, mAge = pairs[j] if j >= 0 else [0, 0]
            score, age = pairs[i]
            res = 0
            if not (score > mScore and age < mAge):
                res = dfs(i + 1, i) + score  # add score
            dp[(i, j)] = max(res, dfs(i + 1, j))  # skip score
            return dp[(i, j)]

        return dfs(0, -1)

public class Solution {
    private int[][] pairs;
    private int[][] dp;

    public int bestTeamScore(int[] scores, int[] ages) {
        int n = scores.length;
        pairs = new int[n][2];
        for (int i = 0; i < n; i++) {
            pairs[i][0] = scores[i];
            pairs[i][1] = ages[i];
        }
        Arrays.sort(pairs, (a, b) -> a[0] == b[0] ? Integer.compare(a[1], b[1]) : Integer.compare(a[0], b[0]));

        dp = new int[n][n + 1];
        for (int[] row : dp) {
            Arrays.fill(row, -1);
        }

        return dfs(0, -1);
    }

    private int dfs(int i, int j) {
        if (i == pairs.length) {
            return 0;
        }
        if (dp[i][j + 1] != -1) {
            return dp[i][j + 1];
        }

        int mScore = j >= 0 ? pairs[j][0] : 0;
        int mAge = j >= 0 ? pairs[j][1] : 0;
        int score = pairs[i][0];
        int age = pairs[i][1];

        int res = 0;
        if (!(score > mScore && age < mAge)) {
            res = dfs(i + 1, i) + score;
        }
        dp[i][j + 1] = Math.max(res, dfs(i + 1, j));
        return dp[i][j + 1];
    }
}

class Solution {
private:
    vector<pair<int, int>> pairs;
    vector<vector<int>> dp;

public:
    int bestTeamScore(vector<int>& scores, vector<int>& ages) {
        int n = scores.size();
        pairs.resize(n);
        for (int i = 0; i < n; i++) {
            pairs[i] = {scores[i], ages[i]};
        }
        sort(pairs.begin(), pairs.end());

        dp = vector<vector<int>>(n, vector<int>(n + 1, -1));
        return dfs(0, -1);
    }

private:
    int dfs(int i, int j) {
        if (i == pairs.size()) {
            return 0;
        }
        if (dp[i][j + 1] != -1) {
            return dp[i][j + 1];
        }

        int mScore = j >= 0 ? pairs[j].first : 0;
        int mAge = j >= 0 ? pairs[j].second : 0;
        int score = pairs[i].first;
        int age = pairs[i].second;

        int res = 0;
        if (!(score > mScore && age < mAge)) {
            res = dfs(i + 1, i) + score;
        }
        dp[i][j + 1] = max(res, dfs(i + 1, j));
        return dp[i][j + 1];
    }
};

class Solution {
    /**
     * @param {number[]} scores
     * @param {number[]} ages
     * @return {number}
     */
    bestTeamScore(scores, ages) {
        const n = scores.length;
        const pairs = [];
        for (let i = 0; i < n; i++) {
            pairs.push([scores[i], ages[i]]);
        }
        pairs.sort((a, b) => (a[0] === b[0] ? a[1] - b[1] : a[0] - b[0]));

        const dp = Array.from({ length: n }, () => new Array(n + 1).fill(-1));

        const dfs = (i, j) => {
            if (i === n) {
                return 0;
            }
            if (dp[i][j + 1] !== -1) {
                return dp[i][j + 1];
            }

            const [mScore, mAge] = j >= 0 ? pairs[j] : [0, 0];
            const [score, age] = pairs[i];

            let res = 0;
            if (!(score > mScore && age < mAge)) {
                res = dfs(i + 1, i) + score;
            }
            dp[i][j + 1] = Math.max(res, dfs(i + 1, j));
            return dp[i][j + 1];
        };

        return dfs(0, -1);
    }
}

public class Solution {
    private int[][] pairs;
    private int[,] dp;

    public int BestTeamScore(int[] scores, int[] ages) {
        int n = scores.Length;
        pairs = new int[n][];
        for (int i = 0; i < n; i++) {
            pairs[i] = new int[] { scores[i], ages[i] };
        }
        Array.Sort(pairs, (a, b) => a[0] == b[0] ? a[1].CompareTo(b[1]) : a[0].CompareTo(b[0]));

        dp = new int[n, n + 1];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= n; j++) {
                dp[i, j] = -1;
            }
        }

        return Dfs(0, -1);
    }

    private int Dfs(int i, int j) {
        if (i == pairs.Length) return 0;
        if (dp[i, j + 1] != -1) return dp[i, j + 1];

        int mScore = j >= 0 ? pairs[j][0] : 0;
        int mAge = j >= 0 ? pairs[j][1] : 0;
        int score = pairs[i][0];
        int age = pairs[i][1];

        int res = 0;
        if (!(score > mScore && age < mAge)) {
            res = Dfs(i + 1, i) + score;
        }
        dp[i, j + 1] = Math.Max(res, Dfs(i + 1, j));
        return dp[i, j + 1];
    }
}

class Solution {
    private lateinit var pairs: Array<IntArray>
    private lateinit var dp: Array<IntArray>

    fun bestTeamScore(scores: IntArray, ages: IntArray): Int {
        val n = scores.size
        pairs = Array(n) { intArrayOf(scores[it], ages[it]) }
        pairs.sortWith(compareBy({ it[0] }, { it[1] }))

        dp = Array(n) { IntArray(n + 1) { -1 } }
        return dfs(0, -1)
    }

    private fun dfs(i: Int, j: Int): Int {
        if (i == pairs.size) return 0
        if (dp[i][j + 1] != -1) return dp[i][j + 1]

        val mScore = if (j >= 0) pairs[j][0] else 0
        val mAge = if (j >= 0) pairs[j][1] else 0
        val score = pairs[i][0]
        val age = pairs[i][1]

        var res = 0
        if (!(score > mScore && age < mAge)) {
            res = dfs(i + 1, i) + score
        }
        dp[i][j + 1] = maxOf(res, dfs(i + 1, j))
        return dp[i][j + 1]
    }
}

class Solution {
    private var pairs: [[Int]] = []
    private var dp: [[Int]] = []

    func bestTeamScore(_ scores: [Int], _ ages: [Int]) -> Int {
        let n = scores.count
        pairs = (0..<n).map { [scores[$0], ages[$0]] }
        pairs.sort { $0[0] == $1[0] ? $0[1] < $1[1] : $0[0] < $1[0] }

        dp = Array(repeating: Array(repeating: -1, count: n + 1), count: n)
        return dfs(0, -1)
    }

    private func dfs(_ i: Int, _ j: Int) -> Int {
        if i == pairs.count { return 0 }
        if dp[i][j + 1] != -1 { return dp[i][j + 1] }

        let mScore = j >= 0 ? pairs[j][0] : 0
        let mAge = j >= 0 ? pairs[j][1] : 0
        let score = pairs[i][0]
        let age = pairs[i][1]

        var res = 0
        if !(score > mScore && age < mAge) {
            res = dfs(i + 1, i) + score
        }
        dp[i][j + 1] = max(res, dfs(i + 1, j))
        return dp[i][j + 1]
    }
}

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(n ^ 2)$

2. Dynamic Programming (Bottom-Up)

Intuition

Instead of recursion, we can build the solution iteratively. After sorting players by score, for each player we look at all previous players and check if we can extend their team. If the current player's age is greater than or equal to a previous player's age, we can add the current player to that team without causing a conflict. We track the maximum score ending at each player position.

Algorithm

Create pairs of (score, age) for each player and sort them by score, then by age.
Initialize a dp array where dp[i] represents the maximum score of a valid team ending with player i.
For each player i, iterate through all previous players j. If age[i] >= age[j], update dp[i] = max(dp[i], score[i] + dp[j]).
Return the maximum value in the dp array.

class Solution:
    def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:
        pairs = [[scores[i], ages[i]] for i in range(len(scores))]
        pairs.sort()
        dp = [pairs[i][0] for i in range(len(pairs))]

        for i in range(len(pairs)):
            mScore, mAge = pairs[i]
            for j in range(i):
                score, age = pairs[j]
                if mAge >= age:
                    dp[i] = max(dp[i], mScore + dp[j])

        return max(dp)

public class Solution {
    public int bestTeamScore(int[] scores, int[] ages) {
        int n = scores.length;
        int[][] pairs = new int[n][2];
        for (int i = 0; i < n; i++) {
            pairs[i][0] = scores[i];
            pairs[i][1] = ages[i];
        }
        Arrays.sort(pairs, (a, b) -> a[0] == b[0] ? Integer.compare(a[1], b[1]) : Integer.compare(a[0], b[0]));

        int[] dp = new int[n];
        for (int i = 0; i < n; i++) {
            dp[i] = pairs[i][0];
        }

        for (int i = 0; i < n; i++) {
            int mScore = pairs[i][0], mAge = pairs[i][1];
            for (int j = 0; j < i; j++) {
                int score = pairs[j][0], age = pairs[j][1];
                if (mAge >= age) {
                    dp[i] = Math.max(dp[i], mScore + dp[j]);
                }
            }
        }

        int maxScore = 0;
        for (int score : dp) {
            maxScore = Math.max(maxScore, score);
        }
        return maxScore;
    }
}

class Solution {
public:
    int bestTeamScore(vector<int>& scores, vector<int>& ages) {
        int n = scores.size();
        vector<pair<int, int>> pairs(n);
        for (int i = 0; i < n; i++) {
            pairs[i] = {scores[i], ages[i]};
        }
        sort(pairs.begin(), pairs.end());

        vector<int> dp(n);
        for (int i = 0; i < n; i++) {
            dp[i] = pairs[i].first;
        }

        for (int i = 0; i < n; i++) {
            int mScore = pairs[i].first, mAge = pairs[i].second;
            for (int j = 0; j < i; j++) {
                int score = pairs[j].first, age = pairs[j].second;
                if (mAge >= age) {
                    dp[i] = max(dp[i], mScore + dp[j]);
                }
            }
        }

        return *max_element(dp.begin(), dp.end());
    }
};

class Solution {
    /**
     * @param {number[]} scores
     * @param {number[]} ages
     * @return {number}
     */
    bestTeamScore(scores, ages) {
        const n = scores.length;
        const pairs = [];
        for (let i = 0; i < n; i++) {
            pairs.push([scores[i], ages[i]]);
        }
        pairs.sort((a, b) => (a[0] === b[0] ? a[1] - b[1] : a[0] - b[0]));

        const dp = new Array(n).fill(0);
        for (let i = 0; i < n; i++) {
            dp[i] = pairs[i][0];
        }

        for (let i = 0; i < n; i++) {
            const [mScore, mAge] = pairs[i];
            for (let j = 0; j < i; j++) {
                const [score, age] = pairs[j];
                if (mAge >= age) {
                    dp[i] = Math.max(dp[i], mScore + dp[j]);
                }
            }
        }

        return Math.max(...dp);
    }
}

public class Solution {
    public int BestTeamScore(int[] scores, int[] ages) {
        int n = scores.Length;
        int[][] pairs = new int[n][];
        for (int i = 0; i < n; i++) {
            pairs[i] = new int[] { scores[i], ages[i] };
        }
        Array.Sort(pairs, (a, b) => a[0] == b[0] ? a[1].CompareTo(b[1]) : a[0].CompareTo(b[0]));

        int[] dp = new int[n];
        for (int i = 0; i < n; i++) {
            dp[i] = pairs[i][0];
        }

        for (int i = 0; i < n; i++) {
            int mScore = pairs[i][0], mAge = pairs[i][1];
            for (int j = 0; j < i; j++) {
                int score = pairs[j][0], age = pairs[j][1];
                if (mAge >= age) {
                    dp[i] = Math.Max(dp[i], mScore + dp[j]);
                }
            }
        }

        return dp.Max();
    }
}

class Solution {
    fun bestTeamScore(scores: IntArray, ages: IntArray): Int {
        val n = scores.size
        val pairs = Array(n) { intArrayOf(scores[it], ages[it]) }
        pairs.sortWith(compareBy({ it[0] }, { it[1] }))

        val dp = IntArray(n) { pairs[it][0] }

        for (i in 0 until n) {
            val mScore = pairs[i][0]
            val mAge = pairs[i][1]
            for (j in 0 until i) {
                val age = pairs[j][1]
                if (mAge >= age) {
                    dp[i] = maxOf(dp[i], mScore + dp[j])
                }
            }
        }

        return dp.maxOrNull() ?: 0
    }
}

class Solution {
    func bestTeamScore(_ scores: [Int], _ ages: [Int]) -> Int {
        let n = scores.count
        var pairs = (0..<n).map { [scores[$0], ages[$0]] }
        pairs.sort { $0[0] == $1[0] ? $0[1] < $1[1] : $0[0] < $1[0] }

        var dp = pairs.map { $0[0] }

        for i in 0..<n {
            let mScore = pairs[i][0]
            let mAge = pairs[i][1]
            for j in 0..<i {
                let age = pairs[j][1]
                if mAge >= age {
                    dp[i] = max(dp[i], mScore + dp[j])
                }
            }
        }

        return dp.max() ?? 0
    }
}

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(n)$

3. Dynamic Programming (Segment Tree)

Intuition

The bottom-up approach has O(n^2) complexity because we check all previous players for each new player. We can optimize this using a segment tree. Since we only care about players with ages less than or equal to the current player's age, we can query the segment tree for the maximum dp value among all ages in the range [0, current_age]. After processing each player, we update the segment tree with the new dp value at that age index.

Algorithm

Create pairs of (score, age) for each player and sort them by score, then by age.
Compress the ages to consecutive indices (coordinate compression) for efficient segment tree usage.
Build a segment tree that supports range maximum queries and point updates.
For each player in sorted order, query the segment tree for the maximum score among all ages less than or equal to the current age.
Update the current player's dp value as the query result plus their score.
Update the segment tree at the current age index with this dp value.
Track and return the overall maximum score.

class SegmentTree:
    def __init__(self, N):
        self.n = N
        while (self.n & (self.n - 1)) != 0:
            self.n += 1
        self.build()

    def build(self):
        self.tree = [0] * (2 * self.n)

    def update(self, i, val):
        pos = self.n + i
        self.tree[pos] = max(self.tree[pos], val)
        pos >>= 1
        while pos >= 1:
            self.tree[pos] = max(self.tree[pos << 1], self.tree[pos << 1 | 1])
            pos >>= 1

    def query(self, l, r):
        res = 0
        l += self.n
        r += self.n + 1
        while l < r:
            if l & 1:
                res = max(res, self.tree[l])
                l += 1
            if r & 1:
                r -= 1
                res = max(res, self.tree[r])
            l >>= 1
            r >>= 1
        return res

class Solution:
    def bestTeamScore(self, scores: list[int], ages: list[int]) -> int:
        pairs = [[scores[i], ages[i]] for i in range(len(scores))]
        pairs.sort()

        dp = [pairs[i][0] for i in range(len(pairs))]
        unique_ages = sorted({ age for _, age in pairs })
        ageId = { val: idx for idx, val in enumerate(unique_ages) }

        segtree = SegmentTree(len(pairs))

        res = 0
        for i in range(len(pairs)):
            mScore, mAge = pairs[i]
            idx = ageId[mAge]
            j = segtree.query(0, idx)
            dp[i] = j + mScore
            segtree.update(idx, dp[i])
            res = max(res, dp[i])

        return res

class SegmentTree {
    private int n;
    private int[] tree;

    public SegmentTree(int N) {
        n = N;
        while ((n & (n - 1)) != 0) {
            n++;
        }
        build();
    }

    private void build() {
        tree = new int[2 * n];
    }

    public void update(int i, int val) {
        int pos = n + i;
        tree[pos] = Math.max(tree[pos], val);
        pos >>= 1;
        while (pos >= 1) {
            tree[pos] = Math.max(tree[pos << 1], tree[pos << 1 | 1]);
            pos >>= 1;
        }
    }

    public int query(int l, int r) {
        int res = 0;
        l += n;
        r += n + 1;
        while (l < r) {
            if ((l & 1) == 1) {
                res = Math.max(res, tree[l]);
                l++;
            }
            if ((r & 1) == 1) {
                r--;
                res = Math.max(res, tree[r]);
            }
            l >>= 1;
            r >>= 1;
        }
        return res;
    }
}

public class Solution {
    public int bestTeamScore(int[] scores, int[] ages) {
        int n = scores.length;
        int[][] pairs = new int[n][2];
        for (int i = 0; i < n; i++) {
            pairs[i][0] = scores[i];
            pairs[i][1] = ages[i];
        }
        Arrays.sort(pairs, (a, b) -> a[0] == b[0] ? Integer.compare(a[1], b[1]) : Integer.compare(a[0], b[0]));

        int[] dp = new int[n];
        for (int i = 0; i < n; i++) {
            dp[i] = pairs[i][0];
        }

        Set<Integer> uniqueAgesSet = new TreeSet<>();
        for (int[] pair : pairs) {
            uniqueAgesSet.add(pair[1]);
        }
        List<Integer> uniqueAges = new ArrayList<>(uniqueAgesSet);
        Map<Integer, Integer> ageId = new HashMap<>();
        for (int i = 0; i < uniqueAges.size(); i++) {
            ageId.put(uniqueAges.get(i), i);
        }

        SegmentTree segtree = new SegmentTree(uniqueAges.size());

        int res = 0;
        for (int i = 0; i < n; i++) {
            int mScore = pairs[i][0];
            int mAge = pairs[i][1];
            int idx = ageId.get(mAge);
            int j = segtree.query(0, idx);
            dp[i] = j + mScore;
            segtree.update(idx, dp[i]);
            res = Math.max(res, dp[i]);
        }

        return res;
    }
}

class SegmentTree {
private:
    int n;
    vector<int> tree;

public:
    SegmentTree(int N) {
        n = N;
        while ((n & (n - 1)) != 0) {
            n++;
        }
        build();
    }

    void build() {
        tree.resize(2 * n, 0);
    }

    void update(int i, int val) {
        int pos = n + i;
        tree[pos] = max(tree[pos], val);
        pos >>= 1;
        while (pos >= 1) {
            tree[pos] = max(tree[pos << 1], tree[pos << 1 | 1]);
            pos >>= 1;
        }
    }

    int query(int l, int r) {
        int res = 0;
        l += n;
        r += n + 1;
        while (l < r) {
            if (l & 1) {
                res = max(res, tree[l]);
                l++;
            }
            if (r & 1) {
                r--;
                res = max(res, tree[r]);
            }
            l >>= 1;
            r >>= 1;
        }
        return res;
    }
};

class Solution {
public:
    int bestTeamScore(vector<int>& scores, vector<int>& ages) {
        int n = scores.size();
        vector<pair<int, int>> pairs(n);
        for (int i = 0; i < n; i++) {
            pairs[i] = {scores[i], ages[i]};
        }
        sort(pairs.begin(), pairs.end());

        vector<int> dp(n);
        for (int i = 0; i < n; i++) {
            dp[i] = pairs[i].first;
        }

        set<int> uniqueAgesSet;
        for (auto& pair : pairs) {
            uniqueAgesSet.insert(pair.second);
        }
        vector<int> uniqueAges(uniqueAgesSet.begin(), uniqueAgesSet.end());
        map<int, int> ageId;
        for (int i = 0; i < uniqueAges.size(); i++) {
            ageId[uniqueAges[i]] = i;
        }

        SegmentTree segtree(uniqueAges.size());

        int res = 0;
        for (int i = 0; i < n; i++) {
            int mScore = pairs[i].first;
            int mAge = pairs[i].second;
            int idx = ageId[mAge];
            int j = segtree.query(0, idx);
            dp[i] = j + mScore;
            segtree.update(idx, dp[i]);
            res = max(res, dp[i]);
        }

        return res;
    }
};

class SegmentTree {
    /**
     * @constructor
     * @param {number} N
     */
    constructor(N) {
        this.n = N;
        while ((this.n & (this.n - 1)) !== 0) {
            this.n++;
        }
        this.build();
    }

    /**
     * @return {void}
     */
    build() {
        this.tree = new Array(2 * this.n).fill(0);
    }

    /**
     * @param {number} i
     * @param {number} val
     * @return {void}
     */
    update(i, val) {
        let pos = this.n + i;
        this.tree[pos] = Math.max(this.tree[pos], val);
        pos >>= 1;
        while (pos >= 1) {
            this.tree[pos] = Math.max(
                this.tree[pos << 1],
                this.tree[(pos << 1) | 1],
            );
            pos >>= 1;
        }
    }

    /**
     * @param {number} l
     * @param {number} r
     * @return {number}
     */
    query(l, r) {
        let res = 0;
        l += this.n;
        r += this.n + 1;
        while (l < r) {
            if (l & 1) {
                res = Math.max(res, this.tree[l]);
                l++;
            }
            if (r & 1) {
                r--;
                res = Math.max(res, this.tree[r]);
            }
            l >>= 1;
            r >>= 1;
        }
        return res;
    }
}

class Solution {
    /**
     * @param {number[]} scores
     * @param {number[]} ages
     * @return {number}
     */
    bestTeamScore(scores, ages) {
        const n = scores.length;
        const pairs = [];

        for (let i = 0; i < n; i++) {
            pairs.push([scores[i], ages[i]]);
        }
        pairs.sort((a, b) => (a[0] === b[0] ? a[1] - b[1] : a[0] - b[0]));

        const dp = new Array(n).fill(0);
        for (let i = 0; i < n; i++) {
            dp[i] = pairs[i][0];
        }

        const uniqueAges = [...new Set(pairs.map((p) => p[1]))].sort(
            (a, b) => a - b,
        );
        const ageId = new Map();
        uniqueAges.forEach((val, idx) => ageId.set(val, idx));

        const segtree = new SegmentTree(uniqueAges.length);

        let res = 0;

        for (let i = 0; i < n; i++) {
            const [mScore, mAge] = pairs[i];
            const idx = ageId.get(mAge);
            const j = segtree.query(0, idx);
            dp[i] = j + mScore;
            segtree.update(idx, dp[i]);
            res = Math.max(res, dp[i]);
        }

        return res;
    }
}

public class SegmentTree {
    private int n;
    private int[] tree;

    public SegmentTree(int N) {
        n = N;
        while ((n & (n - 1)) != 0) n++;
        tree = new int[2 * n];
    }

    public void Update(int i, int val) {
        int pos = n + i;
        tree[pos] = Math.Max(tree[pos], val);
        pos >>= 1;
        while (pos >= 1) {
            tree[pos] = Math.Max(tree[pos << 1], tree[(pos << 1) | 1]);
            pos >>= 1;
        }
    }

    public int Query(int l, int r) {
        int res = 0;
        l += n; r += n + 1;
        while (l < r) {
            if ((l & 1) == 1) res = Math.Max(res, tree[l++]);
            if ((r & 1) == 1) res = Math.Max(res, tree[--r]);
            l >>= 1; r >>= 1;
        }
        return res;
    }
}

public class Solution {
    public int BestTeamScore(int[] scores, int[] ages) {
        int n = scores.Length;
        int[][] pairs = new int[n][];
        for (int i = 0; i < n; i++) {
            pairs[i] = new int[] { scores[i], ages[i] };
        }
        Array.Sort(pairs, (a, b) => a[0] == b[0] ? a[1].CompareTo(b[1]) : a[0].CompareTo(b[0]));

        var uniqueAges = pairs.Select(p => p[1]).Distinct().OrderBy(x => x).ToList();
        var ageId = new Dictionary<int, int>();
        for (int i = 0; i < uniqueAges.Count; i++) {
            ageId[uniqueAges[i]] = i;
        }

        var segtree = new SegmentTree(uniqueAges.Count);
        int res = 0;

        for (int i = 0; i < n; i++) {
            int mScore = pairs[i][0], mAge = pairs[i][1];
            int idx = ageId[mAge];
            int j = segtree.Query(0, idx);
            int dp = j + mScore;
            segtree.Update(idx, dp);
            res = Math.Max(res, dp);
        }

        return res;
    }
}

type SegmentTree struct {
    n    int
    tree []int
}

func NewSegmentTree(N int) *SegmentTree {
    n := N
    for n&(n-1) != 0 {
        n++
    }
    return &SegmentTree{n: n, tree: make([]int, 2*n)}
}

func (st *SegmentTree) Update(i, val int) {
    pos := st.n + i
    if val > st.tree[pos] {
        st.tree[pos] = val
    }
    pos >>= 1
    for pos >= 1 {
        st.tree[pos] = max(st.tree[pos<<1], st.tree[pos<<1|1])
        pos >>= 1
    }
}

func (st *SegmentTree) Query(l, r int) int {
    res := 0
    l += st.n
    r += st.n + 1
    for l < r {
        if l&1 == 1 {
            if st.tree[l] > res {
                res = st.tree[l]
            }
            l++
        }
        if r&1 == 1 {
            r--
            if st.tree[r] > res {
                res = st.tree[r]
            }
        }
        l >>= 1
        r >>= 1
    }
    return res
}

func bestTeamScore(scores []int, ages []int) int {
    n := len(scores)
    pairs := make([][2]int, n)
    for i := 0; i < n; i++ {
        pairs[i] = [2]int{scores[i], ages[i]}
    }
    sort.Slice(pairs, func(i, j int) bool {
        if pairs[i][0] == pairs[j][0] {
            return pairs[i][1] < pairs[j][1]
        }
        return pairs[i][0] < pairs[j][0]
    })

    ageSet := make(map[int]struct{})
    for _, p := range pairs {
        ageSet[p[1]] = struct{}{}
    }
    uniqueAges := make([]int, 0, len(ageSet))
    for age := range ageSet {
        uniqueAges = append(uniqueAges, age)
    }
    sort.Ints(uniqueAges)
    ageId := make(map[int]int)
    for i, age := range uniqueAges {
        ageId[age] = i
    }

    segtree := NewSegmentTree(len(uniqueAges))
    res := 0

    for i := 0; i < n; i++ {
        mScore, mAge := pairs[i][0], pairs[i][1]
        idx := ageId[mAge]
        j := segtree.Query(0, idx)
        dp := j + mScore
        segtree.Update(idx, dp)
        if dp > res {
            res = dp
        }
    }

    return res
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

class SegmentTree(N: Int) {
    private var n: Int = N
    private var tree: IntArray

    init {
        while (n and (n - 1) != 0) n++
        tree = IntArray(2 * n)
    }

    fun update(i: Int, value: Int) {
        var pos = n + i
        tree[pos] = maxOf(tree[pos], value)
        pos = pos shr 1
        while (pos >= 1) {
            tree[pos] = maxOf(tree[pos shl 1], tree[pos shl 1 or 1])
            pos = pos shr 1
        }
    }

    fun query(l: Int, r: Int): Int {
        var left = l + n
        var right = r + n + 1
        var res = 0
        while (left < right) {
            if (left and 1 == 1) res = maxOf(res, tree[left++])
            if (right and 1 == 1) res = maxOf(res, tree[--right])
            left = left shr 1
            right = right shr 1
        }
        return res
    }
}

class Solution {
    fun bestTeamScore(scores: IntArray, ages: IntArray): Int {
        val n = scores.size
        val pairs = Array(n) { intArrayOf(scores[it], ages[it]) }
        pairs.sortWith(compareBy({ it[0] }, { it[1] }))

        val uniqueAges = pairs.map { it[1] }.distinct().sorted()
        val ageId = uniqueAges.withIndex().associate { it.value to it.index }

        val segtree = SegmentTree(uniqueAges.size)
        var res = 0

        for (i in 0 until n) {
            val mScore = pairs[i][0]
            val mAge = pairs[i][1]
            val idx = ageId[mAge]!!
            val j = segtree.query(0, idx)
            val dp = j + mScore
            segtree.update(idx, dp)
            res = maxOf(res, dp)
        }

        return res
    }
}

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity: $O(n)$

Common Pitfalls

Sorting by Age Instead of Score

The problem requires sorting by score (with age as a tiebreaker) so that we only need to check if ages are compatible. Sorting by age first leads to a more complex conflict check and often incorrect results.

# Wrong: pairs.sort(key=lambda x: x[1])  # sorting by age
# Correct: pairs.sort()  # sort by score first, then age

Misunderstanding the Conflict Condition

A conflict occurs when a younger player has a strictly higher score than an older player. The condition is NOT simply "different ages with different scores." Players with the same age never conflict, regardless of scores.

Forgetting to Include the Player's Own Score

When computing the DP value for a player, you must add their own score to the best team score from compatible previous players. Forgetting to add the current player's score gives an answer that is always one player short.