雇用K名工人的最低成本

题目描述

有一组工人，每个工人的工作质量为 quality[i]，期望的最低工资为 wage[i]。现在需要雇佣 K 名工人来完成一项工作。其中，每名工人只能接受与其工作质量相同或更高的工资。求解需要满足工人数量为 K 的情况下，所需的最小总工资。

解题步骤

为了解决最小成本雇佣工人的问题，我们可以使用贪心算法来解决。贪心算法的思路是优先选择工资效益最高的工人。

我们按照以下步骤进行解题：

1. 创建一个数组 ratios[]，用于存储每个工人的工资与工作质量的比率（wage[i]/quality[i]）。
2. 将工人按照 ratios[] 的升序进行排序，以便能够从低比率到高比率依次选择工人。
3. 创建一个最小堆 pq，用于维护当前选择的 K 名工人的最高工资。
4. 初始化变量 sumQuality 为 0，用于累计当前选择的工人的工作质量之和。
5. 遍历排序后的工人列表，对于每个工人：
   • 将其加入堆 pq。
   • 将其工作质量添加到 sumQuality。
   • 如果堆 pq 中的工人数量超过 K，则移除堆顶的工人（即最高工资的工人）。
   • 如果堆 pq 中的工人数量等于 K，计算当前总工资 currWage，即当前选择的 K 名工人中的最高工资乘以 sumQuality。
     • 如果 currWage 小于当前的最小总工资 minWage，更新 minWage 的值。
6. 遍历结束后，minWage 就是所需的最小总工资。

以下是使用贪心算法解决最小成本雇佣工人问题的算法框架：

function mincostToHireWorkers(quality, wage, K) {
  const workers = [];
  const n = quality.length;

  for (let i = 0; i < n; i++) {
    const ratio = wage[i] / quality[i];
    workers.push([quality[i], wage[i], ratio]);
  }

  workers.sort((a, b) => a[2] - b[2]);

  let sumQuality = 0;
  let minWage = Infinity;
  const pq = new MaxHeap();

  for (let i = 0; i < n; i++) {
    const [currQuality, currWage, ratio] = workers[i];

    pq.insert(currQuality);
    sumQuality += currQuality;

    if (pq.size() > K) {
      sumQuality -= pq.extractMax();
    }

    if (pq.size() === K) {
      const currWageSum = sumQuality * ratio;
      minWage = Math.min(minWage, currWageSum);
    }
  }

  return minWage;
}