Best Team With No Conflicts — LeetCode 1626 Python Solution

The problem

You are the manager of a basketball team. For the upcoming tournament, you want to choose the team with the highest overall score.

Example

Input

scores = [1,3,5,10,15], ages = [1,2,3,4,5]

Output

34

Explanation

You can choose all the players.

Python solution

class Solution:
    def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:
        arr = sorted(zip(scores, ages))
        n = len(arr)
        f = [0] * n
        for i, (score, age) in enumerate(arr):
            for j in range(i):
                if age >= arr[j][1]:
                    f[i] = max(f[i], f[j])
            f[i] += score
        return max(f)

Complexity

Pattern: Sorting

Spend O(n log n) once to buy an ordering that makes the rest of the problem trivial. LeetCode 1626. Best Team With No Conflicts is filed here because LeetCode tags it Sorting, which is the vocabulary this hub collects.

The sorting guide has the Python template for the pattern and the 401 LeetCode problems that use it.

Related problems