857. K人の労働者を雇う最小コスト

https://leetcode.com/problems/minimum-cost-to-hire-k-workers/

これは超難しいです。私の休日を奪わないでください。

これは私の総当たり解答です。時間制限超過のため受理されませんでした。

let bin = (n) =>
  new Array(n)
    .fill(0)
    .map((v, i) => i)
    .reduce((a, v) => [...a, ...a.map((c) => [...c, v])], [[]]);

let comb = (n, k) => bin(n).filter((c) => c.length === k);

let value = (quality, wage, choice) => {
  let unit = Math.max(...choice.map((c) => wage[c] / quality[c]));
  return choice.map((c) => quality[c] * unit).reduce((a, v) => a + v, 0);
};

var mincostToHireWorkers = function (quality, wage, k) {
  return Math.min(
    ...comb(quality.length, k).map((choice) => value(quality, wage, choice)),
  );
};

次に、公式解答を読みました。JavaScriptで書き直しました。初めてPriorityQueueを使いました。

var mincostToHireWorkers = function (quality, wage, k) {
  let n = quality.length;
  let cost = Infinity;
  let tq = 0;
  let wqratios = quality.map((q, i) => [wage[i] / q, q]);
  wqratios.sort((a, b) => a[0] - b[0]);
  let hq = new PriorityQueue({
    compare: (a, b) => a - b,
  });
  for (let [r, q] of wqratios) {
    hq.enqueue(-q);
    tq += q;
    if (hq.size() > k) {
      tq += hq.dequeue();
    }
    if (hq.size() === k) {
      cost = Math.min(cost, tq * r);
    }
  }
  return cost;
};

しかし、この解答の仕組みを理解するのはまだ難しいです。明日の休日も勉強に費やすことになりそうです。