Minimum Cost to Hire M Candidates

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’.

As mentioned in Approach 1, there must be at least one candidate, ‘REPRESENTATIVE’ who is paid exactly equals to his/her expected salary, otherwise, it will not be optimum. The ‘REPRESENTATIVE’ will allow us to easily choose the rest of the ‘M - 1’ candidates.

After fixing the ‘REPRESENTATIVE’, any candidate ‘i’ would be paid:

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

From Rule 2,

       SALARY[i] >= EXPECTED_SALARY[i]

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

or, EXPECTED_SALARY[REPRESENTATIVE]) / SKILL[REPRESENTATIVE] >= EXPECTED_SALARY[i] / SKILL[i]

This means that the ratio of “EXPECTED_SALARY / SKILL” for the ‘REPRESENTATIVE’ must be the highest in the group. So, in a group of ‘M’ candidates, the candidate with the highest “EXPECTED_SALARY / SKILL” ratio will be ‘REPRESENTATIVE’.

Also, the total cost of hiring ‘M’ candidates is

     COST = (EXPECTED_SALARY[REPRESENTATIVE]) / SKILL[REPRESENTATIVE]) * (SKILL[0] + SKILL[1] + . . . + SKILL[M-1])

or, COST = (EXPECTED_SALARY[REPRESENTATIVE]) / SKILL[REPRESENTATIVE]) * (total sum of skills of ‘M’ candidates)

Let us say, EXPECTED_SALARY[REPRESENTATIVE]) / SKILL[REPRESENTATIVE] = REPRESENTATIVE_RATIO.

So to minimize the total cost, we want a small ratio. For every ratio, we find the minimum possible total skill of ‘M’ candidates.

In this way, we will repeat the process and we can find the minimum total cost.

Algorithm:

• Create a vector of pairs, ‘CANDIDATES’ with the first data type as ‘double’ and second data type as ‘int’. The ‘CANDIDATES’ will store the “EXPECTED_SALARY / SKILL” ratio and corresponding skill of the candidate.
• Run a loop for CANDIDATE = 0 to N - 1.
  • Push ‘{EXPECTED_SALARY[CANDIDATE] / SKILL[CANDIDATE], SKILL[CANDIDATE]}’ in the ‘CANDIDATES’.
• Sort the ‘CANDIDATES’ in ascending order of their first value.
• Declare two double variables, ‘MIN_COST’ and ‘TOTAL_SKILLS’ and assign ‘TOTAL_SKILLS’ by zero. The ‘MIN_COST’ will store the final minimum cost to hire ‘M’ candidates and ‘TOTAL_SKILLS’ will store the skills of ‘M’ candidates.
• Declare a max heap, ‘MAX_HEAP’.
• Run a loop for int i = 0 to M - 1.
  • Add ‘CANDIDATES[i].SECOND’ in the ‘TOTAL_SKILLS’.
  • Push ‘CANDIDATES[i].SECOND’ in the ‘MAX_HEAP’.
• Declare a double variable, ‘REPRESENTATIVE_RATIO’ and assign ‘CANDIDATES[i].FIRST’ into it.
• Update ‘MIN_COST’ by ‘REPRESENTATIVE_RATIO * TOTAL_SKILL’.
• Run a loop for i = M to ‘N - 1’.
  • Declare an integer variable, ‘MAX_SKILL_TILL_NOW’ and initialize it with ‘MAX_HEAP.TOP()’.
  • Declare an integer variable, ‘CURRENT_CANDIDATE_SKILL’ and initialize it with ‘CANDIDATES[i].SECOND’.
  • If CURRENT_CANDIDATE_SKILL < MAX_SKILL_TILL_NOW.
    • Pop the top element of ‘MAX_HEAP’.
    • Push the ‘CURRENT_CANDIDATE_SKILL’ in ‘MAX_HEAP’.
    • Add ‘CURRENT_CANDIDATE_SKILL’ to the ‘TOTAL_SKILL’ and subtract ‘MAX_SKILL_TILL_NOW’ from the ‘TOTAL_COST’.
  • Update the ‘REPRESENTATIVE_RATIO’ by ‘CANDIDATES[i].FIRST’.
  • Assign ‘MIN(REPRESENTATIVE_RATIO * TOTAL_SKILL, MIN_COST)’ to the ‘MIN_COST’.
• In the end, return ‘MIN_COST’.