Minimum Cost to Hire M Candidates

Hard
0/120
Average time to solve is 50m
7 upvotes
Asked in companies
SalesforceShareChatApple

Problem statement

You are the HR of the Ninja team and planning to hire ‘M’ candidates out of ‘N’ candidates to form a paid group. The candidates have been evaluated on the basis of their skills and have been asked for their minimum salary expectations. So, you are given two arrays, ‘SKILL’ and ‘EXPECTED_SALARY’, where ‘SKILL[i]’ and ‘EXPECTED_SALARY[i]’ represent the skill and minimum salary expectation of ‘i-th’ candidate, respectively. You have to consider the following two rules for hiring a group of ‘M’ candidates:

1) Every candidate in the paid group should be paid in the ratio of their skill compared to other candidates in the paid group.
2) The minimum salary expectation of every candidate in the paid group should be fulfilled.

You have to return the minimum amount of money required to hire ‘M’ candidates as per the above-mentioned rules.

Note:

Answers which are within the range 10^-6 of the correct answer will be considered correct.
Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of input contains an integer 'T' representing the number of test cases.

The first line of each test case contains an integer ‘N’ representing the number of total candidates.

The second line of each test case contains ‘N’ space-separated integers representing the elements of the ‘SKILL’ array.

The third line of each test case contains ‘N’ space-separated integers representing the elements of ‘EXPECTED_SALARY’ array.

The last line of each test case contains an integer ‘M’ representing the number of candidates to be hired.

Output Format:

For each test case, return the minimum cost to hire ‘M’ candidates.

The output of each test case will be printed in a separate line.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 5
1 <= M <= N <= 10^3
1 <= SKILL[ i ] <= 10^3
1 <= EXPECTED_SALARY[ i ] <= 10^3

Time limit: 1 second

Sample Input 1:

2
4
18 20 15 50
40 42 30 70
2
5
42 3 23 50 20 
50 5 10 45 35
3

Sample Output 1:

73.333333
80.500000

Explanation of Sample Output 1:

Test Case 1 :  

We can hire the 1st and 3rd candidate with minimum cost. The 1st candidate will be paid 40 and the 3rd candidate will be paid 33.333333, resulting in a total cost of 73.333333.


Test Case 2 : 

We can hire the 2nd, 3rd and 5th candidates with minimum cost. The 2nd candidate will be paid 5.250000, the 3rd candidate will be paid 40.250000 and the 5th candidate will be paid 35.000000, resulting in a total cost of 80.500000.

Sample Input 2:

2
6
3 10 8 13 25 7
5 8 12 15 20 7
3
4
17 16 15 4
20 15 17 3
1

Sample Output 2:

30.000000
3.000000
Hint

It is intuitive that at least one candidate will be paid exactly equals to his/her minimum salary expectation for minimising the total cost. Using this information as per Rule 1, can you scale the salaries of other ‘M - 1’ candidates?

Approaches (2)
Greedy Approach

We have two rules to follow:

  1. SKILL[i] : SKILL[j] = SALARY[i] : SALARY[j]
  2. SALARY[i] >= EXPECTED_SALARY[i]

Where 1 <= i, j <= N.

 

To minimise the total cost, at least one candidate will be paid exactly equals to his/her minimum salary expectation. Otherwise, we will be paying everyone more than their expectation resulting in an increase in total cost, which is not desirable.

 

Now as per Rule 1, we can scale the salary of all other candidates if we fix the salary of one candidate. Let us say that the candidate who is paid exactly equals his/her minimum salary is termed as ‘REPRESENTATIVE’. So, Rule 1 is settled.

As per Rule 2,

 

      SKILL[i] : SKILL[REPRESENTATIVE] = SALARY[i] : SALARY[REPRESENTATIVE]

or, SKILL[i] : SKILL[REPRESENTATIVE] = SALARY[i] : EXPECTED_SALARY[REPRESENTATIVE]

or, (SKILL[i] : SKILL[REPRESENTATIVE]) * EXPECTED_SALARY[REPRESENTATIVE] = SALARY[i]

or, SALARY[i] = SKILL[i] * (EXPECTED_SALARY[REPRESENTATIVE]) / SKILL[REPRESENTATIVE])

or, SALARY[i] = SKILL[i] * REPRESENTATIVE_RATIO

Where REPRESENTATIVE_RATIO = (EXPECTED_SALARY[REPRESENTATIVE]) / SKILL[REPRESENTATIVE]).

 

For every ‘REPRESENTATIVE’, we will find the salaries of all other candidates using the formula mentioned above. After finding the salary of every candidate, we will choose the lowest ‘M - 1’ salary candidates among ‘N - 1’ candidates. And store the total cost (including salary of the representative candidate) in a variable, ‘COST’.

We will repeat the above procedure for every candidate considering them as ‘REPRESENTATIVE’ and store the minimum of all ‘COST’ in ‘MIN_COST’.

 

Algorithm:

  • Declare a double variable, ‘MIN_COST’ and initialize it to ‘DBL_MAX’ to store the final minimum cost to hire ‘M’ candidates.
  • Run a loop for REPRESENTATIVE = 0 to N - 1.
    • Declare a double variable, ‘REPRESENTATIVE_RATIO’ and assign ‘EXPECTED_SALARY[REPRESENTATIVE] / SKILL[REPRESENTATIVE]’.
    • Declare a double variable, ‘COST’ and initialize it with zero.
    • Declare a vector of double, ‘HIRED_CANDIDATE_SALARY’ to store the salary of candidates who can be hired.
    • Run a loop for candidate = 0 to N - 1.
      • Declare a double variable, ‘SALARY’ and assign ‘SKILL[CANDIDATE] * REPRESENTATIVE_RATIO’ that stores the SALARY to be paid to the ‘CANDIDATE’.
      • If SALARY >= EXPECTED_SALARY[CANDIDATE] that shows that salary to be paid is greater than the candidate’s expected salary.
        • So, insert the ‘SALARY’ of the ‘CANDIDATE’ in the ‘HIRED_CANDIDATE_SALARY’.
    • If the  size of ‘HIRED_CANDIDATES_SALARY’ < M that shows that ‘M’ candidates cannot be hired for the current ‘REPRESENTATIVE’.
      • So, skip the below steps.
    • Declare a max heap, ‘MAX_HEAP’.
    • Run a loop for int i = 0 to M - 1.
      • Push the ‘HIRED_CANDIDATES_SALARY[i]’ in ‘MAX_HEAP’.
      • Add ‘HIRED_CANDIDATES_SALARY[i]’ in the ‘COST’.
    • Run a loop for int i = M to ‘HIRED_CANDIDATES_SALARY[i].size() - 1’.
      • Declare a double variable, ‘CURRENT_CANDIDATE_SALARY’ and initialize it with ‘HIRED_CANDIDATES_SALARY[i]’.
      • Declare a double variable, ‘MAX_SALARY_TILL_NOW’ and initialize it with ‘MAX_HEAP.TOP()’.
      • If CURRENT_CANDIDATE_SALARY < MAX_SALARY_TILL_NOW.
        • Pop the top element of ‘MAX_HEAP’.
        • Push the ‘CURRENT_CANDIDATE_SALARY’ in ‘MAX_HEAP’.
        • Add ‘CURRENT_CANDIDATE_SALARY’ to the ‘COST’ and subtract ‘MAX_SALARY_TILL_NOW’ from the ‘COST’.
    • Assign ‘MIN(COST, MIN_COST)’ to the ‘MIN_COST’.
  • In the end, return ‘MIN_COST’.
Time Complexity

O((N ^ 2) * (log(M))), where ‘N’ is the total number of candidates and ‘M’ is the number of candidates required to be hired.

 

It is because the first loop runs ‘N’ iterations. In every iteration,  the second for loop runs ‘N’ times and push-pop operation in the max heap will also occur ‘N’ times, in the worst case. The push-pop operation in the max heap will take O(log(M)) time as there will be ‘M’ elements in the heap at any instant.

Hence, overall time complexity = O(N ^ 2) + O(N ^ 2 * (log(M)) = O(N ^ 2 * (log(M)).

Space Complexity

O(N + M), where ‘N’ is the total number of candidates and ‘M’ is the number of candidates required to be hired.

 

Since the ‘HIRED_CANDIDATES_SALARY’ requires O(N) space and ‘MAX_HEAP’ requires O(M) space. Hence, overall space complexity = O(N) + O(M) = O(N + M).

Code Solution
(100% EXP penalty)
Minimum Cost to Hire M Candidates
Full screen
Console