What is the key pattern used to solve the Minimum Cost to Hire K Workers problem?

The problem follows the greedy choice pattern, where we select workers based on their wage-to-quality ratio and use a priority queue to manage the smallest qualities.

How does the priority queue help in the Minimum Cost to Hire K Workers problem?

The priority queue helps by efficiently tracking the k workers with the lowest qualities while maintaining the total cost, ensuring optimal worker selection.

What is the time complexity of the solution for the Minimum Cost to Hire K Workers problem?

The time complexity is O(n log n + n log k), where n is the number of workers, and k is the number of workers to be hired.

What are the common pitfalls when solving the Minimum Cost to Hire K Workers problem?

Common pitfalls include failing to maintain the wage-quality invariant, using inefficient selection methods, and misunderstanding the cost calculation.

What are some variations of the Minimum Cost to Hire K Workers problem?

Variations include adjusting the number of workers hired, changing input sizes, and adding new restrictions on worker qualities and wage ratios.

#857

Hard

auto_awesome贪心·invariant

LeetCode 题解工作台

雇佣 K 名工人的最低成本

有 n 名工人。给定两个数组 quality 和 wage ，其中， quality[i] 表示第 i 名工人的工作质量，其最低期望工资为 wage[i] 。现在我们想雇佣 k 名工人组成一个工资组。在雇佣一组 k 名工人时，我们必须按照下述规则向他们支付工资：对工资组中的每名工人，应…

数组贪心排序堆（优先队列）

题目描述

有 n 名工人。给定两个数组 quality 和 wage ，其中，quality[i] 表示第 i 名工人的工作质量，其最低期望工资为 wage[i] 。

现在我们想雇佣 k 名工人组成一个 工资组。在雇佣一组 k 名工人时，我们必须按照下述规则向他们支付工资：

对工资组中的每名工人，应当按其工作质量与同组其他工人的工作质量的比例来支付工资。
工资组中的每名工人至少应当得到他们的最低期望工资。

给定整数 k ，返回 组成满足上述条件的付费群体所需的最小金额 。与实际答案误差相差在 10^-5 以内的答案将被接受。

示例 1：

输入： quality = [10,20,5], wage = [70,50,30], k = 2
输出： 105.00000
解释： 我们向 0 号工人支付 70，向 2 号工人支付 35。

示例 2：

输入： quality = [3,1,10,10,1], wage = [4,8,2,2,7], k = 3
输出： 30.66667
解释： 我们向 0 号工人支付 4，向 2 号和 3 号分别支付 13.33333。

提示：

n == quality.length == wage.length
1 <= k <= n <= 10⁴
1 <= quality[i], wage[i] <= 10⁴

lightbulb

解题思路

方法一：贪心 + 优先队列（大根堆）

我们假设选取了某一个工资组，总工作质量为 tot，总支付金额为 c。每个工人的工作质量为 $q_i$ ，工资为 $w_i$ 。那么，对于此工资组的每个工人，均满足 $c\times \frac{q_i}{tot} \ge w_i$ 。即 $c\ge tot\times \frac{w_i}{q_i}$ 。

在总工作质量 tot 固定的情况下，支付的金额取决于权重 $\frac{w_i}{q_i}$ 的最大值。

我们可以从小到大枚举权重 $\frac{w_i}{q_i}$ 作为工资组的最大值，此时工资组其他人员只需要在权重小于等于这个值的集合中，选取工作质量最小的 $k-1$ 名工人来组成工资组即可。因此，可以用优先队列（最大堆）维护工作质量最小的 $k-1$ 名工人。

时间复杂度 $O(n\log n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 是工人数。

相似题目：

1383. 最大的团队表现值

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def mincostToHireWorkers(
        self, quality: List[int], wage: List[int], k: int
    ) -> float:
        t = sorted(zip(quality, wage), key=lambda x: x[1] / x[0])
        ans, tot = inf, 0
        h = []
        for q, w in t:
            tot += q
            heappush(h, -q)
            if len(h) == k:
                ans = min(ans, w / q * tot)
                tot += heappop(h)
        return ans

speed

复杂度分析

指标	值
时间	O(n \log n + n \log k)
空间	O(n + k)

psychology

面试官常问的追问

外企场景

question_mark
Look for understanding of greedy algorithms and their application to optimization problems.
question_mark
Check if the candidate can handle edge cases with varying worker qualities and wage expectations.
question_mark
Evaluate the ability to use sorting and priority queues efficiently in solving complex problems.

warning

常见陷阱

外企场景

error
Failing to properly maintain the invariant between wage and quality ratios, which can lead to incorrect cost calculations.
error
Overlooking the need to use a priority queue for efficient selection of workers, resulting in inefficient solutions.
error
Confusing the total wage with the total cost, failing to account for the proportional wage adjustment based on quality.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Modify the problem to hire more or fewer workers, testing the algorithm's scalability.
arrow_right_alt
Change the constraints to larger arrays, examining the efficiency of the solution under higher input sizes.
arrow_right_alt
Add additional restrictions on worker quality or wage ratios to test if the greedy strategy still holds.

help

常见问题

外企场景

继续练习

#1054 距离相等的条形码 #632 最小区间 #630 课程表 III