857. Minimum Cost to Hire K Workers

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

This is super hard. Please don’t take away my day off.

This is my brute-force solution. It's not accepted because of Time Limit Exceeded.

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))
  );
};

Next, I read the official solution. I rewrote it in JavaScript. I used the PriorityQueue for the first time.

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;
};

However, I'm still hard to understand the mechanism of this solution. I will miss my day off tomorrow.