Last Updated: 4 Sep, 2022

Cost To Company

Moderate

Solve now

Problem statement

Sam is a recruiter for an MNC. He had recruited the best talents this hiring season. There are ‘N’ candidates, where ‘N’ is even. His task is to divide them into ‘N’/2 teams, each team consisting of 2 candidates - a junior dev and senior dev, and the problem-solving skills of the senior dev must be greater than the junior dev.

The candidates are sorted in decreasing order of their problem-solving skills.

Each candidate has a SALARY expectation for the junior role and senior role.

Sam wants to know the minimum cost to the company for the optimal arrangement of candidates in teams.

The salary expectation of the same candidate is higher for senior roles than the junior roles but after the arrangement in teams, the salary of the junior may be higher than the senior.

Example:

Input: ‘N’ = 4 ,  'SALARY' =  [[8000,10000],[16000,25000],[10000,11000],[16000,20000]]

Output: 53000
Explanation:
Array elements represent the SALARY expectations of candidates sorted in decreasing order of problem-solving skills.

The first and second candidates can be put in a team, with the senior role for the first, so 10000+16000 = 26000.
The third and fourth candidates can be put in a team, with the senior role for the third, so 11000+16000 = 27000.
Thus, The Cost to Company =  26000 + 27000 = 53000.

Input Format :

The first line of the input contains an integer denoting the number of test cases.

The first line of each test case contains an even integer, 'N’, denoting the number of candidates.

The next ‘N’ lines of each test case contain 2 space-separated integers denoting SALARY expectations for the junior role and senior role in order.

Output format :

Return an integer denoting the minimum cost to the company.

Constraints :

1  <= T <= 10
2  <= N <= 10000
1 <= SALARY[i][0] < SALARY[i][1] <= 100000
Time Limit: 1 sec

Solve now

Approaches

01 Approach

The brute force solution for the problem lies in generating all the permutations for pairing the candidates and returning the minimum cost to the company.

We can store the salary expectations along with the problem-solving skills for each candidate in ‘sal’ array with ‘N’ rows for every candidate and 3 columns for problem-setting skills, and expectation for junior and senior roles. We will then generate all the permutations of the ‘sal’ and for each permutation, we will pair them up by looking at the problem-solving skills and update the minimum to the answer.

The steps are as follows :

Initialize and assign a huge value to the ‘answer’ initially.
Store problem-setting skills and salary expectations in the ‘sal’ array.
For all permutations of ‘sal’ array
- Initialize ‘sum’ with 0.
- For ‘idx’ in range 1 to ‘N’
  - if(sal[idx][2] < sal[idx+1][2])
    - Add sal[idx][1] and sal[idx+1][0] to sum.
  - Else
    - Add sal[idx+1][1] and sal[idx][0] to sum.
- if(sum < answer)
  - answer = sum
Return answer.

Solve now

02 Approach

The first candidate should be assigned to a senior role. Now from the second candidate, we can minimize the cost to the company by assigning him the senior or junior role. The problem can be solved using dynamic programming.

States: 2 State DP - role(0 or 1) and index.

DP[ role ][ index ] = Minimum cost to the company if the current index candidate is assigned the role 0 or 1 (senior or junior).

Transition: Let ‘idx’ be the current index in range 1 to ’N’/2, ‘idxBefore’ be the indexes in range 1 to idx.

DP[role][idxBefore]=min(DP[role][idxBefore-1]+SALARY[idx+idxBefore-1][0],DP[!role][idxBefore]+SALARY[idx+idxBefore-1][1])

For every value of idx in the range [1,’N’/2].

The steps are as follows :

Assign the DP table 2xN with 0 initially and a variable ‘role’ with 0.
For ‘idx’ in range 1 to ‘N’/2
- Assign DP[role][idx] with DP[!role][idx]+SALARY[idx-1][1] .
- For ‘idxBefore’ in range 1 to ‘idx’
  - If ‘idx’ and ‘idxBefore’ are not equal
    - DP[ role ][ idxBefore ] = min(DP[ role ][ idxBefore-1]+SALARY[idx+idxBefore-1][0],DP[!role][idxBefore]+SALARY[idx+idxBefore-1][1])
  - else
    - DP[ role ][ idxBefore ] = DP[ role ][ idxBefore-1]+SALARY[idx+idxBefore-1][0]
- role = !role.

3. Return DP[!role][N/2].

Solve now