MediumNo. 1626
Best Team With No Conflicts — LeetCode 1626 Python Solution
- Pattern
- Sorting
- Topics
- Array, Dynamic Programming, Sorting
- Reading time
- 2 min
- Source
- leetcode.com
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
- Time
- O(n·m) (typical)
- Space · auxiliary
- O(n·m)or optimized
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
| No. | Problem | Difficulty |
|---|---|---|
| 0368 | Largest Divisible Subset | Medium |
| 0435 | Non-overlapping Intervals | Medium |
| 0472 | Concatenated Words | Hard |
| 0646 | Maximum Length of Pair Chain | Medium |
| 0975 | Odd Even Jump | Hard |
| 1262 | Greatest Sum Divisible by Three | Medium |
Frequently asked questions
- How hard is LeetCode 1626. Best Team With No Conflicts?
LeetCode 1626. Best Team With No Conflicts is rated Medium on LeetCode.
- What topics does LeetCode 1626. Best Team With No Conflicts cover?
LeetCode 1626. Best Team With No Conflicts is tagged Array, Dynamic Programming and Sorting on LeetCode.