Best Team With No Conflicts — Algorithms&Visualizations

Federico Feresini

Follow

Nov 26, 2020 · 5 min read

Introduction
In this article, I’ll be trying to describe a rather common Dynamic Programming technique used to solve an interesting coding challenge taken from one of the contests that you can find on LeetCode.
As DP (Dynamic Programming) can be a tricky concept, sometimes hard to grasp, I’ve endeavored to produce some pictures which will help to get the point across.

The problem
I came across this problem while taking a LeetCode contest. The title of the problem is Best Team With No Conflicts and here below the problem description:

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
Input: scores = [1, 8, 9, 12, 11, 8] ages = [10, 40, 50, 50, 40, 30]
Output: 40
The team with the biggest score comprising only not-conflicting players is the one made of all the players but the one at position 2 (score=0, age=50).

For those who are already familiar with these kinds of problems, it’s not going to be very hard figuring out a solution. But if you are not, no worries, we will be going step-by-step towards the final solution.

First Approach

The problem asks us to compare different players and make a decision based on their ages and scores. It’s surely worth sorting the players by their age.

Now we can consider one player at a time and see what is the best team for him (by best team I mean the one that would make the score of that team the biggest)

Player 1 is the first one we are gonna consider. For the time being, we don’t have any teams, so the best Player 1 can do, is create a team by himself and the best score he can get is its own score.

Player 2 has two choices, playing alone, o joining the team of Player 1. The second choice produces a bigger total score, so we will go with that.

Player 3 has three different options: (a)playing alone with a score of 14. (b) Joining Player 2 team, as he doesn’t conflict with Player 2.
Hey, wait a minute! He can’t join that team, because Player 1 would conflict with Player 3 in that team.

It seemed such a great approach, but we need to fix it. Let’s dig a bit deeper into the issue. The problem is that Player 2 joins Player 1, and we lose the team made by Player 2 alone, which is exactly the team Player 3 would like to join. On the other side, stored in BestScore[i] we still have information about the team made by Player 1 only. How can we fix it?

Second Approach
With this above intuition, we came up with the idea of sorting players of the same age by ascending score.
Why should that work? Well, first off that would avoid the previously experienced problem, and this is already a good starting point, but let’s try to figure out the general idea.

We already know that players of the same age can play together; Consequently, we foresee that every player will have an outbound arrow point to the team comprising the players of the same age previously visited

That being said, what happens when a Player of a different age shows up?
Let’s display all the possibilities:

This picture should have eradicated any doubts!

Whatever is the score of Player 5, we always have enough information stored into Best Score to compute the best team for Player 5.

Let’s analyze the bottom-left picture. Player 5 matches all the previous teams. It can be assigned to the teams:
[Player 1]
[Player 1, Player 2]
[Player 1, Player 2, Player 3]
[Player 1, Player 2, Player 3, Player 4]

From all the possibilities, we only save into Best Score the biggest total score. Note that we don’t need to know who are the Players of the team that Player 5 joins.

Let’s apply this new approach to the previous example to see if it actually works fine:

This seems the correct approach to follow. Let’s jump into the code.

Code

Conclusion
I hope you enjoyed this article ad hopefully learned something.

“We know accurately only when we know little; with knowledge doubt enters.” — Johann Wolfgang von Goethe