1626. Best Team With No Conflicts

Todo -

• Add Notes
• Add Code
• Add Diagram
• Explain Thought Process

Problem Link:

https://leetcode.com/problems/best-team-with-no-conflicts/

Notes:

A very good Dynamic Programming Problem.

1. Sort the pair of age and scores according to scores ascending.

2. Backtrack on the above sorted array.

3. Memoise the solution.

Code:

// method 1: using normal dp recursive.
    
    int n;
    vector<pair<int, int>> in;
    vector<vector<int>> dp;
    
    int solve (int idx, int max_age_till_now) {
        
        if (idx == n)   return 0;
        
        if (dp[idx][max_age_till_now] != -1) {
            return dp[idx][max_age_till_now];
        }
        
        int a = 0, b = 0;
        
        // choose current index if valid.
        // if age of current is greater than or equal to max age till here.
        
        if (in[idx].second >= max_age_till_now) {
            a = in[idx].first + solve (idx+1, max(max_age_till_now, in[idx].second));
        }
        
        // we dont want to choose
        
        b = solve (idx+1, max_age_till_now);

        return dp[idx][max_age_till_now] = max(a, b);
    }
    
    int bestTeamScore(vector<int>& scores, vector<int>& ages) {
        
        n = scores.size();
        in = vector<pair<int, int>> (n);
        dp = vector<vector<int>> (n+1, vector<int> (1005, -1));
        for (int i=0; i<n; ++i) {
            in[i] = {scores[i], ages[i]};
        }
        
        sort (in.begin(), in.end(), [] (const auto &p1, const auto &p2) {
            return p1.first < p2.first || (p1.first == p2.first && p1.second < p2.second);
        });
        
        int ans = solve (0, 0);
        return ans;
    }