1626. Best Team With No Conflicts LeetCode Solution
In this guide, you will get 1626. Best Team With No Conflicts LeetCode Solution with the best time and space complexity. The solution to Best Team With No Conflicts problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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.
1626. Best Team With No Conflicts LeetCode Solution in C++
struct Player {
int age;
int score;
Player(int age, int score) : age(age), score(score) {}
};
class Solution {
public:
int bestTeamScore(vector<int>& scores, vector<int>& ages) {
const int n = scores.size();
vector<Player> players;
// dp[i] := the maximum score of choosing the players[0..i] with the
// players[i] being selected
vector<int> dp(n);
for (int i = 0; i < n; ++i)
players.emplace_back(ages[i], scores[i]);
ranges::sort(players, [](const Player& a, const Player& b) {
return a.age == b.age ? a.score > b.score : a.age > b.age;
});
for (int i = 0; i < n; ++i) {
// For each player, choose it first.
dp[i] = players[i].score;
// players[j].age >= players[i].age since we sort in descending order.
// So, we only have to check that players[j].score >= players[i].score.
for (int j = 0; j < i; ++j)
if (players[j].score >= players[i].score)
dp[i] = max(dp[i], dp[j] + players[i].score);
}
return ranges::max(dp);
}
}; /* code provided by PROGIEZ */
1626. Best Team With No Conflicts LeetCode Solution in Java
class Solution {
public int bestTeamScore(int[] scores, int[] ages) {
record Player(int age, int score) {}
final int n = scores.length;
Player[] players = new Player[n];
// dp[i] := the maximum score of choosing the players[0..i] with the players[i] being selected
int[] dp = new int[n];
for (int i = 0; i < n; ++i)
players[i] = new Player(ages[i], scores[i]);
Arrays.sort(players,
(a, b) //
-> a.age == b.age ? Integer.compare(b.score, a.score)
: Integer.compare(b.age, a.age));
for (int i = 0; i < n; ++i) {
// For each player, choose it first.
dp[i] = players[i].score;
// players[j].age >= players[i].age since we sort in descending order.
// So, we only have to check that players[j].score >= players[i].score.
for (int j = 0; j < i; ++j)
if (players[j].score >= players[i].score)
dp[i] = Math.max(dp[i], dp[j] + players[i].score);
}
return Arrays.stream(dp).max().getAsInt();
}
} // code provided by PROGIEZ
1626. Best Team With No Conflicts LeetCode Solution in Python
