Best Team With No Conflicts Solution in C++

Problem Description

So, you think you can build the best team without any conflicts? Well, welcome to the “Best Team With No Conflicts” problem on LeetCode! Imagine you’re the coach of a sports team, and you have a bunch of players with different ages and scores. Your task is to select a team such that no player has a higher score than another player who is older. Sounds simple, right? Just like trying to convince your friends to play Monopoly without arguing over the rules!

In this problem, you need to maximize the total score of the selected players while ensuring that the age and score conditions are met. So, if you thought picking a team was as easy as picking a pizza topping, think again!

Code Solution


struct Player {
  int age;
  int score;
  Player(int age, int score) : age(age), score(score) {}
};

class Solution {
 public:
  int bestTeamScore(vector& scores, vector& ages) {
    const int n = scores.size();
    vector players;
    vector 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) {
      dp[i] = 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);
  }
};

Approach

The approach taken in this solution is quite straightforward yet effective. First, we create a Player struct to hold the age and score of each player. We then sort the players based on their age (in descending order) and score (also in descending order for players of the same age). This way, we can ensure that when we select a player, all previously selected players are either younger or have a lower score.

Next, we use dynamic programming to calculate the maximum score possible by iterating through the sorted players and updating our dp array, which keeps track of the best scores achievable up to each player.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(n²), where n is the number of players.
Space Complexity	O(n), for storing the `dp` array and the `players` vector.

Real-World Example

Imagine you’re assembling a team for a trivia night. You want to pick the smartest players, but you also want to avoid any awkwardness that might arise from having a know-it-all who is older than everyone else. You can only choose players who either have a lower score or are younger. This is exactly what the “Best Team With No Conflicts” problem is about—selecting the best team while avoiding conflicts!