Best Team With No Conflicts - Practice Coding Problems

Best Team With No Conflicts - Problem

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 arrays 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.

Input & Output

Example 1 — Basic Team Selection

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

› Output: 34

💡 Note: All players have increasing age and score, so we can select all: 1+3+5+10+15 = 34

Example 2 — Conflict Resolution

$ Input: scores = [4,5,6,5], ages = [2,1,2,1]

› Output: 16

💡 Note: Sort by age: [(1,5), (1,5), (2,4), (2,6)]. Best team is players with scores [5,6,5] = 16

Example 3 — Single Player

$ Input: scores = [1], ages = [1]

› Output: 1

💡 Note: Only one player available, so team score is 1

Constraints

1 ≤ ages.length ≤ 1000
ages.length == scores.length
1 ≤ ages[i] ≤ 1000
1 ≤ scores[i] ≤ 10⁶

Visualization

Tap to expand

Understanding the Visualization

Input

Players with their ages and scores

Process

Find team with max score avoiding younger-higher conflicts

Output

Maximum possible team score

Key Takeaway

🎯 Key Insight: Sort by age first to transform conflict checking into a maximum sum increasing subsequence problem

Asked in

G Google 15 f Facebook 12 a Amazon 8 M Microsoft 6

The key insight is to sort players by age first, transforming this into a maximum sum increasing subsequence problem. After sorting, we can use dynamic programming where dp[i] represents the maximum team score ending with player i. Best approach is Sort + DP with Time: O(n²), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Sort + Dynamic Programming	O(n²)	O(n)	Sort by age, then apply maximum sum increasing subsequence DP
Brute Force - All Combinations	O(2^n × n²)	O(n)	Try every possible subset and check for conflicts
Optimized Sort + DP	O(n²)	O(n)	Enhanced sorting strategy for better conflict resolution

Sort + Dynamic Programming — Algorithm Steps

Sort players by age (keeping score-age pairs)
Use DP where dp[i] = max score ending at position i
For each position, consider all previous valid players

Visualization

Tap to expand

Step-by-Step Walkthrough

Sort by Age

Arrange players by increasing age to simplify conflict checking

Apply DP

For each player, find max score including previous compatible players

Build Solution

DP[i] represents best team ending with player i

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    int age;
    int score;
} Player;

int comparePlayer(const void* a, const void* b) {
    Player* p1 = (Player*)a;
    Player* p2 = (Player*)b;
    if (p1->age == p2->age) {
        return p1->score - p2->score;
    }
    return p1->age - p2->age;
}

int solution(int* scores, int* ages, int n) {
    // Create pairs and sort by age, then by score
    Player players[1000];
    for (int i = 0; i < n; i++) {
        players[i].age = ages[i];
        players[i].score = scores[i];
    }
    qsort(players, n, sizeof(Player), comparePlayer);
    
    // DP: dp[i] = maximum score ending at position i
    int dp[1000];
    
    for (int i = 0; i < n; i++) {
        dp[i] = players[i].score;  // At minimum, take current player
        
        // Check all previous players
        for (int j = 0; j < i; j++) {
            // Can include player j if their score <= current player's score
            if (players[j].score <= players[i].score) {
                int newScore = dp[j] + players[i].score;
                if (newScore > dp[i]) {
                    dp[i] = newScore;
                }
            }
        }
    }
    
    int maxScore = 0;
    for (int i = 0; i < n; i++) {
        if (dp[i] > maxScore) {
            maxScore = dp[i];
        }
    }
    return maxScore;
}

int main() {
    char line[1000];
    int scores[1000], ages[1000], n = 0;
    
    // Parse scores array
    fgets(line, sizeof(line), stdin);
    char* token = strtok(line, "[,]\n");
    while (token != NULL) {
        scores[n++] = atoi(token);
        token = strtok(NULL, "[,]\n");
    }
    
    // Parse ages array
    fgets(line, sizeof(line), stdin);
    token = strtok(line, "[,]\n");
    int i = 0;
    while (token != NULL) {
        ages[i++] = atoi(token);
        token = strtok(NULL, "[,]\n");
    }
    
    printf("%d\n", solution(scores, ages, n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Sorting takes O(n log n), DP has nested loops of O(n²), so total is O(n²)

⚠ Quadratic Growth

Space Complexity

O(n)

DP array stores one value per player, plus space for sorted pairs

⚡ Linearithmic Space

32.4K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Sort + Dynamic Programming — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler