There are n workers. You are given two integer arrays quality and wage where quality[i] is the quality of the ith worker and wage[i] is the minimum wage expectation for the ith worker.

We want to hire exactly k workers to form a paid group. To hire a group of k workers, we must pay them according to the following rules:

1. Every worker in the paid group should be paid in the ratio of their quality compared to other workers in the paid group.
2. Every worker in the paid group must be paid at least their minimum-wage expectation.

Given the integer k, return the least amount of money needed to form a paid group satisfying the above conditions. Answers within 10-5 of the actual answer will be accepted.

Example 1:

Input: quality = [10,20,5], wage = [70,50,30], k = 2
Output: 105.00000
Explanation: We pay 70 to 0th worker and 35 to 2nd worker.

Example 2:

Input: quality = [3,1,10,10,1], wage = [4,8,2,2,7], k = 3
Output: 30.66667
Explanation: We pay 4 to 0th worker, 13.33333 to 2nd and 3rd workers separately.

Constraints:

• n == quality.length == wage.length
• 1 <= k <= n <= 104
• 1 <= quality[i], wage[i] <= 104

Ideas:

首先理解题意， 两个条件

条件1： k个员工的薪水能力比ratio要一样，那么，要优先选择ratio高的；

person1: wage = 10, quality = 5, ratio = 10/5 = 2
person2: wage = 5, quality = 10, ratio = 5/10 = 0.5

看上面两个例子，虽然按道理来说我们要先选性价比高的，也就是person2， 但是如果按照person2给了min wage 5，那么，person1只能得到 5 * （person2 的ratio = 0.5）= 2.5， 会跟第二个条件矛盾（必须要满足min wage， 所以要先选性价比低的；）那么就将（ratio, quality, wage）从小到大排， 因为for loop 时，当前的ratio就是最大的ratio；

另外利用一个max Heap， 来存quality， 每次如果超过k个worker，那么就把quality最大的去掉，因为ratio * quality = 要pay的wage；利用-quality去维持minHeap, 另外用一个sumq 来记录当前

max Heap 所有quality的值。

Code:   T: O(n lgn)

class Solution:
    def mincostToHireWorkers(self, quality: List[int], wage: List[int], k: int) -> float:
        workers = sorted((w/q, q, w) for q, w in zip(quality, wage))
        ans = float(‘inf‘)
        pool = []
        sumq = 0
        for ratio, q, w in workers:
            heapq.heappush(pool, -q)
            sumq += q
            
            if len(pool) > k:
                sumq += heapq.heappop(pool)
            
            if len(pool) == k:
                ans = min(ans, ratio * sumq)
        return float(ans)

[LeetCode] 857. Minimum Cost to Hire K Workers_Hard tag: sort, heap