Compute Salary Threshold

EPI 14.10

Description:

Given salaries of different employees and target payroll come up with a cap by which people who get less than that salary dont get affected by people who get more salary than cap get reduced to cap

Example:

Ex. Employee salaray {20,30,40,90,100} and total payroll of 210. Cap should be 60 and new salaries would be {20,30,40,60,60}

Idea:

先对salary排序。然后从少的salary开始，算if curr salary * remainingNum < remainingPayroll, 如果是，可以，如果不是，要算allowedSalary.

Code:

#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

vector<int> salaryThreshold(vector<int> currSalary, int totalPayroll){
    sort(currSalary.begin(), currSalary.end());

    vector<int> result;
    int remainPayroll = totalPayroll;
    int remainNum;
    int allowedSalary;
    for(int i=0; i<currSalary.size(); i++){
        remainNum=currSalary.size()-i;
        if(currSalary[i]*remainNum <= remainPayroll){
            allowedSalary = currSalary[i];
        }
        else{
            allowedSalary = i==currSalary.size()-1? remainPayroll: remainPayroll/remainNum;
        }
        result.push_back(allowedSalary);
        remainPayroll -= allowedSalary;
    }

    return result;
}

int main(){
    vector<int> currSalary ={20,30,40,90,100};
    int totalPayroll=223;

    for(auto elem: salaryThreshold(currSalary, totalPayroll)){
        cout<<elem<<' ';
    }
}