Best Team With No Conflicts
Medium · 1-D Dynamic Programming · Explanation and code example
Dynamic Programming (Segment Tree)
How it works
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.
Steps
- 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
dpvalue as the query result plus their score. - Update the segment tree at the current age index with this
dpvalue. - Track and return the overall maximum score.
Complexity
- Time complexity:
O(n log n) - Space complexity:
O(n)
Things to watch for
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.
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.
Python code example
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
C++ code example
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;
}
};
Source and license
Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.