Optimizing Team Formation with Grade and Age Constraints
Given two arrays, grades[], and ages[], representing the grades and ages of participants in a competition. The goal is to form teams in a way that maximizes the total grade of each team while adhering to specific constraints. The constraints are defined as follows:
- Each participant is characterized by a grade and an age.
- A team is not allowed to have conflicts, meaning that a younger participant cannot have a higher grade than an older participant. However, conflicts do not occur between participants of the same age.
Examples:
Input: grades = [4, 7, 9, 5, 8] ,ages = [1, 2, 3, 1, 2]
Output: 33
Explanation: In this case we can take all the students , and no conflicting situation occurs, as the conflict would have occurred if an older person with a less grade would be in the team with younger person with more grade, both the students with grades 7 and 9 have ages 2 and 3 respectively, and students with age 5, 8 have ages 1 , 2 respectively, considering a team with all of them would not be a problem.Input: grades = [1, 2, 3, 4], ages = [4, 3, 2, 1]
Output: 4
Explanation: In this case we can just take student with grade 4 and age 1 as rest all other combinations would result into conflict.
Approach: To solve the problem follow the below idea:
- Define a global 2D array dp for memoization.
- Implement a recursive function solver that takes i (current student index), and maxage (maximum age in the team), and returns the maximum grade that can be obtained.
- Base case:
- If i exceeds the size of grp, return 0 (no more students to consider).
- If the result for the current ‘i‘ and ‘maxage‘ combination is already calculated, return it.
- If the age of the current student (grp[i][1]) is greater than or equal to maxage, we have two choices:
- Include the current student and recursively call the solver for the next student with updated maxage and incremented grade.
- Skip the current student and call the solver for the next student with the same maxage.
- Return the maximum value between the two choices as the result for this subproblem.
- In the main function, create grades and ages vectors and call the bestTeamGrade function with these vectors as arguments. Print the result.
Below is the implementation for the above approach:
C++14
#include <bits/stdc++.h> using namespace std; // Define a global 2D array for memoization int dp[10005][1001]; // Recursive function to find the maximum grade // for the best team int solver(vector<vector< int > >& grp, int i, int maxage) { // Base case: If 'i' exceeds the size of // 'grp', return 0 if (i >= grp.size()) { return 0; } // If the result for current 'i' and 'maxage' // combination is already calculated, return it if (dp[i][maxage] != -1) return dp[i][maxage]; // If the age of the current student is // greater than or equal to 'maxage', we // have two choices: // 1. Include the current student and // recursively call 'solver' for the next // student with updated 'maxage' and // incremented grade. // 2. Skip the current student and call // 'solver' for the next student with // the same 'maxage'. if (grp[i][1] >= maxage) { return dp[i][maxage] = max(grp[i][0] + solver(grp, i + 1, grp[i][1]), solver(grp, i + 1, maxage)); } // If the age of the current student is less // than 'maxage', skip the current student return dp[i][maxage] = solver(grp, i + 1, maxage); } // Function to find the maximum grade // for the best team int bestTeamGrade(vector< int >& grades, vector< int >& ages) { // Initialize a 2D vector 'grp' where each // element is a vector containing the grade // and age of a student. vector<vector< int > > grp; for ( int i = 0; i < grades.size(); i++) { vector< int > temp; temp.push_back(grades[i]); temp.push_back(ages[i]); grp.push_back(temp); } // Initialize the 'dp' array with -1 // for memoization memset (dp, -1, sizeof (dp)); // Sort the 'grp' vector based on age // in ascending order sort(grp.begin(), grp.end()); // Call the 'solver' function with // initial values return solver(grp, 0, 0); } // Drivers code int main() { // Example 'grades' and 'ages' vectors vector< int > grades = { 1, 2, 3, 4 }; vector< int > ages = { 4, 3, 2, 1 }; // Call the 'bestTeamGrade' function and // print the result cout << bestTeamGrade(grades, ages); return 0; } |
Java
// Java code for the above approach: import java.util.*; class GFG { // Define a global D array for memoization static int [][] dp = new int [ 10005 ][ 1001 ]; // Recursive function to find the maximum grade // for the best team static int solver(List<List<Integer> > grp, int i, int maxage) { // Base case: If 'i' exceeds the size of // 'grp', return 0 if (i >= grp.size()) { return 0 ; } // If the result for current 'i' and 'maxage' // combination is already calculated, return it if (dp[i][maxage] != - 1 ) return dp[i][maxage]; // If the age of the current student is // greater than or equal to 'maxage', we // have two choices: // 1. Include the current student and // recursively call 'solver' for the next // student with updated 'maxage' and // incremented grade. // 2. Skip the current student and call // 'solver' for the next student with // the same 'maxage'. if (grp.get(i).get( 1 ) >= maxage) { return dp[i][maxage] = Math.max(grp.get(i).get( 0 ) + solver(grp, i + 1 , grp.get(i).get( 1 )), solver(grp, i + 1 , maxage)); } // If the age of the current student is less // than 'maxage', skip the current student return dp[i][maxage] = solver(grp, i + 1 , maxage); } // Function to find the maximum grade // for the best team static int bestTeamGrade(List<Integer> grades, List<Integer> ages) { // Initialize a 2D list 'grp' where each // element is a list containing the grade // and age of a student. List<List<Integer> > grp = new ArrayList<>(); for ( int i = 0 ; i < grades.size(); i++) { List<Integer> temp = new ArrayList<>(); temp.add(grades.get(i)); temp.add(ages.get(i)); grp.add(temp); } // Initialize the 'dp' array with -1 // for memoization Arrays.stream(dp).forEach( row -> Arrays.fill(row, - 1 )); // Sort the 'grp' list based on age // in ascending order Collections.sort(grp, (a, b) -> a.get( 0 ) - b.get( 0 )); // Call the 'solver' function with // initial values return solver(grp, 0 , 0 ); } // Drivers code public static void main(String[] args) { // Example 'grades' and 'ages' lists List<Integer> grades = List.of( 1 , 2 , 3 , 4 ); List<Integer> ages = List.of( 4 , 3 , 2 , 1 ); // Call the 'bestTeamGrade' function and // print the result System.out.println(bestTeamGrade(grades, ages)); } } // This code is contributed by ragul21 |
Python3
# Python code for the above approach # Define a global D array for memoization dp = [[ - 1 for _ in range ( 1001 )] for _ in range ( 10005 )] # Recursive function to find the maximum grade # for the best team def solver(grp, i, maxage): # Base case: If 'i' exceeds the size of # 'grp', return 0 if i > = len (grp): return 0 # If the result for the current 'i' and 'maxage' # combination is already calculated, return it if dp[i][maxage] ! = - 1 : return dp[i][maxage] # If the age of the current student is # greater than or equal to 'maxage', we # have two choices: # 1. Include the current student and # recursively call 'solver' for the next # student with updated 'maxage' and # incremented grade. # 2. Skip the current student and call # 'solver' for the next student with # the same 'maxage'. if grp[i][ 1 ] > = maxage: dp[i][maxage] = max ( grp[i][ 0 ] + solver(grp, i + 1 , grp[i][ 1 ]), solver(grp, i + 1 , maxage) ) return dp[i][maxage] # If the age of the current student is less # than 'maxage', skip the current student dp[i][maxage] = solver(grp, i + 1 , maxage) return dp[i][maxage] # Function to find the maximum grade # for the best team def best_team_grade(grades, ages): # Initialize a 2D list 'grp' where each # element is a list containing the grade # and age of a student. grp = [[grades[i], ages[i]] for i in range ( len (grades))] # Initialize the 'dp' array with -1 # for memoization for row in dp: for i in range ( len (row)): row[i] = - 1 # Sort the 'grp' list based on age # in ascending order grp.sort(key = lambda x: x[ 0 ]) # Call the 'solver' function with # initial values return solver(grp, 0 , 0 ) # Driver code if __name__ = = "__main__" : # Example 'grades' and 'ages' lists grades = [ 1 , 2 , 3 , 4 ] ages = [ 4 , 3 , 2 , 1 ] # Call the 'best_team_grade' function and # print the result print (best_team_grade(grades, ages)) |
C#
using System; using System.Collections.Generic; public class Solution { // Define a global 2D array for memoization static int [,] dp = new int [10005, 1001]; // Recursive function to find the maximum grade // for the best team static int Solver(List< int []> grp, int i, int maxAge) { // Base case: If 'i' exceeds the size of 'grp', return 0 if (i >= grp.Count) { return 0; } // If the result for current 'i' and 'maxAge' // combination is already calculated, return it if (dp[i, maxAge] != -1) { return dp[i, maxAge]; } // If the age of the current student is // greater than or equal to 'maxAge', we // have two choices: // 1. Include the current student and // recursively call 'Solver' for the next // student with updated 'maxAge' and // incremented grade. // 2. Skip the current student and call // 'Solver' for the next student with // the same 'maxAge'. if (grp[i][1] >= maxAge) { return (dp[i, maxAge] = Math.Max( grp[i][0] + Solver(grp, i + 1, grp[i][1]), Solver(grp, i + 1, maxAge) )); } // If the age of the current student is less // than 'maxAge', skip the current student return (dp[i, maxAge] = Solver(grp, i + 1, maxAge)); } // Function to find the maximum grade // for the best team static int BestTeamGrade( int [] grades, int [] ages) { // Initialize a List 'grp' where each // element is an array containing the grade // and age of a student. List< int []> grp = new List< int []>(); for ( int i = 0; i < grades.Length; i++) { grp.Add( new int [] { grades[i], ages[i] }); } // Sort the 'grp' list based on age grp.Sort((a, b) => a[0].CompareTo(b[0])); // Call the 'Solver' function with // initial values return Solver(grp, 0, 0); } public static void Main( string [] args) { // Example 'grades' and 'ages' arrays int [] grades = { 1, 2, 3, 4 }; int [] ages = { 4, 3, 2, 1 }; // Initialize dp array with -1 for ( int i = 0; i < 10005; i++) { for ( int j = 0; j < 1001; j++) { dp[i, j] = -1; } } // Call the 'BestTeamGrade' function and // print the result Console.WriteLine(BestTeamGrade(grades, ages)); } } |
Javascript
// Define a global 2D array for memoization let dp = new Array(10005).fill().map(() => new Array(1001).fill(-1)); // Recursive function to find the maximum grade // for the best team function solver(grp, i, maxage) { // Base case: If 'i' exceeds the size of // 'grp', return 0 if (i >= grp.length) { return 0; } // If the result for current 'i' and 'maxage' // combination is already calculated, return it if (dp[i][maxage] !== -1) { return dp[i][maxage]; } // If the age of the current student is // greater than or equal to 'maxage', we // have two choices: // 1. Include the current student and // recursively call 'solver' for the next // student with updated 'maxage' and // incremented grade. // 2. Skip the current student and call // 'solver' for the next student with // the same 'maxage'. if (grp[i][1] >= maxage) { return (dp[i][maxage] = Math.max( grp[i][0] + solver(grp, i + 1, grp[i][1]), solver(grp, i + 1, maxage) )); } // If the age of the current student is less // than 'maxage', skip the current student return (dp[i][maxage] = solver(grp, i + 1, maxage)); } // Function to find the maximum grade // for the best team function bestTeamGrade(grades, ages) { // Initialize a 2D array 'grp' where each // element is an array containing the grade // and age of a student. let grp = []; for (let i = 0; i < grades.length; i++) { grp.push([grades[i], ages[i]]); } // Sort the 'grp' array based on age // in ascending order grp.sort((a, b) => a[0] - b[0]); // Call the 'solver' function with // initial values return solver(grp, 0, 0); } // Example 'grades' and 'ages' arrays let grades = [1, 2, 3, 4]; let ages = [4, 3, 2, 1]; // Call the 'bestTeamGrade' function and // print the result console.log(bestTeamGrade(grades, ages)); |
4
Time Complexity: O(n^2)
Auxiliary space: O(n*m), for the dp array, where ‘n’ is the number of students and ‘m’ is the maximum age.
Contact Us