857.md

Minimum Cost to Hire K Workers

Description

link

---

Solution

• See Code

---

Code

Complexity T : O(nlog(n)) M : O(log(n))

class Solution:
    '''
    思路：
        1. 这种题目首先看到应该思考的就是排序，而其核心在于根据什么排序
        2. 此题的关键在于用指定的比率，ratio去计算这个ratio下最小的group，那么根据ratio排序就可以想出来了
        3. 根据w/q的排序核心在于用任何大的ratio去计算的时候，一定会覆盖掉小ratio下的最低工资，也就是说
            此时我们只需要计算在这个大ratio下，所有比这个ratio还小的workers当中需要支付的最少工资，也就是用这个ratio乘上
            所有有可能的workers当中q总和最小的k个
        4. 那么如何得到q总和最小的k个，自然是用一个size为k的heap来储存即可
    '''
    def mincostToHireWorkers(self, quality: List[int], wage: List[int], K: int) -> float:
        workers = sorted([(w/q, q) for w, q in zip(wage, quality)], key=lambda x: x[0])
        res = float("inf")
        qsum = 0
        hq = []
        for r, q in workers:
            heapq.heappush(hq, -q)
            qsum += q
            if len(hq) > K: qsum += heapq.heappop(hq)
            if len(hq) == K: res = min(res, r*qsum)
        return res