Cost To Company

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
0 upvote

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
4
8000 10000
16000 25000
10000 11000 
16000 20000
4
5000 6000 
6000 7000 
7000 8000
8000 9000
Sample Output 1 :
53000
28000
Explanation Of Sample Input 1 :
Test 1:
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.

Test 2:
The first and second candidates can be put in a team, with the senior role for the first, so 6000+6000 = 12000.
The third and fourth candidates can be put in a team, with the senior role for the third, so 8000+8000 = 16000.
Thus, The Cost to Company =  12000 + 16000 = 28000.
Sample Input 2 :
2
6
5000 6000
7700 8500
6000 7000
7000 8000
9800 10000
8000 9000
2
800 900
1000 1100
Sample Output 2 :
45500
1900
Hint

Check for all permutations.

Approaches (2)
Brute Force

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 :

  1. Initialize and assign a huge value to the ‘answer’ initially.
  2. Store problem-setting skills and salary expectations in the ‘sal’ array.
  3. 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
  4. Return answer.
Time Complexity

O( Nx N! ), Where ‘N’ is the total number of candidates. 

 

It takes (N!) Time to generate all permutations and O(N) to check for the sum for each permutation.

 

Hence the time complexity is O(Nx N ! ). 

Space Complexity

O( N ), Where ‘N’ is the total number of candidates. 

 

As we are using another vector to generate all permutations.

Hence the space complexity is O( N ).

Code Solution
(100% EXP penalty)
Cost To Company
Full screen
Console