[LeetCode]Minimum Cost to Hire K Workers

题目链接

这道题要求两点：

1. 所有人按照quality等比例支付工资
2. 所有人必须满足最低薪酬

所以对于一个K个人的group，这K个人的总工资是取决于两项的：

1. K个人当中，wage/quality的比例最高的
2. K个人的总quality

那么我们可以对所有人按照wage/quality的比例从小到大排序。并且维护一个根据quality比较的max heap。这样当我们遍历到第i个人，他的wage/quality是目前为止最高的，所以其为决定整体工资的第一个因素(后面的元素我们不需要考虑，因为其wage/quality比例更大，放进去当前元素就无法决定最大比例了)。在这个条件下，如果heap中元素大于K个，我们把quality最高的踢掉一直到size为K，这样第二个因素可以控制到最小，那么两者相乘就是当前wage/quality比例下的K个人的最少工资。那么我们遍历完这所有的wage/quality比例，在所有最少工资中取最小的即可。时间复杂度O(N * log N)，代码如下：