LeetCode 857 - Minimum Cost to Hire K Workers

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

There are N workers.  The i-th worker has a quality[i] and a minimum wage expectation wage[i].

Now we want to hire exactly K workers to form a paid group.  When hiring a group of K workers, we must pay them according to the following rules:

1. Every worker in the paid group should be paid in the ratio of their quality compared to other workers in the paid group.
2. Every worker in the paid group must be paid at least their minimum wage expectation.

Return the least amount of money needed to form a paid group satisfying the above conditions.

Example 1:

Input: quality = [10,20,5], wage = [70,50,30], K = 2
Output: 105.00000
Explanation: We pay 70 to 0-th worker and 35 to 2-th worker.

Example 2:

Input: quality = [3,1,10,10,1], wage = [4,8,2,2,7], K = 3
Output: 30.66667
Explanation: We pay 4 to 0-th worker, 13.33333 to 2-th and 3-th workers seperately. 

Note:

1. 1 <= K <= N <= 10000, where N = quality.length = wage.length
2. 1 <= quality[i] <= 10000
3. 1 <= wage[i] <= 10000
4. Answers within 10^-5 of the correct answer will be considered correct.

https://leetcode.com/problems/minimum-cost-to-hire-k-workers/discuss/185085/75ms-Java-with-Explanations

Every worker in the paid group should be paid in the ratio of their quality compared to other workers in the paid group.
->

 quality[i]   money[i] 
 _________  = ________
 quality[j]   money[j]
 
 money[i] / quality[i] = money[j] / quality[j] -- ratio

That is, the group of people should have the same ratio.

Every worker in the paid group must be paid at least their minimum wage expectation.
->

money[i] >= wage[i]
ratio >= wage[i] / quality[i] -- ratio2

->
ratio is at least the maximum ratio2 within the group of K people.

If we keep current candidates in a priority queue as below,

|-- < k candidates--|    
   new worker to join is with higher ratio2

If there are k + 1candidates, we pop the highest quality to reduce total cost.
If there are k candidates, we can calculate the total cost.

    public double mincostToHireWorkers(int[] quality, int[] wage, int K) {       
        int numWorkers = quality.length;
        
        /* qualityRatio[i] = {quality, wage[i] / quality[i]}. */
        double[][] qualityRatio = new double[numWorkers][2];
        
        for (int i = 0; i < numWorkers; i++) {
            qualityRatio[i][0] = quality[i];
            qualityRatio[i][1] = (double) wage[i] / quality[i];
        }
        
        Arrays.sort(qualityRatio, (a, b) -> Double.compare(a[1], b[1]));
        double minSumSalary = Integer.MAX_VALUE;
        int sumQuality = 0;;
        
        /* Always remove maximum quality. */
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> Integer.compare(b, a));
        
        for (int i = 0; i < numWorkers; i++) {
            maxHeap.add((int)qualityRatio[i][0]);
            sumQuality += qualityRatio[i][0];
            if (maxHeap.size() > K) {
                int qualityPolled = maxHeap.poll();
                sumQuality -= qualityPolled;
            }        
            if (maxHeap.size() == K) {
                
                /* Calculate sumSalary. */
                double curRatio = qualityRatio[i][1];
                minSumSalary = Math.min(minSumSalary, sumQuality * curRatio);
            }
        }
        
        return minSumSalary;
    }

https://www.cnblogs.com/lightwindy/p/9795918.html

有N个工人，第i个工人的质量是quality[i]，最小工资期盼是wage[i]，现在想雇K个工人组成一个支付组，返回所需的最小花费。有两个条件：

1. K个工人的质量和给他开的工资的比例是相同的。
2. 每个工人都要满足他的最小期望工资。

解法：最大堆, heapq, PriorityQueue。首先对付工资和质量的比率进行排序wage/quality，同时记录quality，也就是(wage/quality, quality)，代表一个工人情况，比率越大说明工人效率越低。选定的K个人最后要按照相同的比率来支付工资，为了保证每个人的最低工资标准，只能选定比率最高的人的比率来支付工资。每个人的支付工资：wage = ratio * quality，总的支付工资：total wage = ratio * total quality，在ratio相同的情况小，总的quality越小越好。用一个变量result记录最小花费，初始为最大浮点数。循环排序好的工资比率，用一个变量qsum累加quality，用一个最大堆记录当前的quality，堆顶是最大的quality，如果堆长度等于K+1，就弹出quality最大的，同时qsum中去掉这个最大值。堆满足K个工人的时候，每次都计算qsum * ratio，和result比较取小的。

https://blog.csdn.net/fuxuemingzhu/article/details/82942731

每个工人都有自己期望的价性比，雇佣K个工人的时候要满足每个人的实际价性比不低于他的期望，即需要按照K个工人中的最高期望价性比给这K个人开工资。问需要的最少的工资是多少。注意使用的是价性比，不是性价比。因为性价比是我们买东西的时候希望的，而这些工人是出卖自己的劳动力的，因此他们希望得到更高的价性比。而作为选择工人的这一方，我们希望工人的性价比更高点，但是啊得注意，性价比高的工人会被那些性价比低的工人抬高工资，即他也会要求更高的工资，没有工人愿意看到别人好吃懒做还拿高工资，所以性价比高的工人会索要更高的工资，导致自己性价比和好吃懒做的工人一样。

如果理解了上面的那段话，那么我们需要按照价性比来做排序，然后依次遍历，得到K个工人的工资总和。

使用了一个大根堆，来获取K个工人的最大的价性比，作为K个工人的价性比，使用qsum保存K个工人的质量和。要给他们付的工资就是qsum * 最大性价比。

时间复杂度是O(Nlog(N))，空间复杂度是O(N)。

另外C++ priority queue默认是大顶堆，老是记混。。

https://buptwc.com/2018/06/26/Leetcode-857-Minimum-Cost-to-Hire-K-Workers/

1. 这道题有点意思，要雇佣K个人，使得所花钱最少，雇佣需满足两个条件，一是最后给的钱必须成比例，二是不能低于最小值
2. 我们不妨设最后雇佣时给第i个人的钱为p[i]，则对于被选上的K个人来说，都有相同的比例 p[i] / quality[i]（根据条件1）
3. 也就是说一旦我们选定了比例 r，那么最后选的K个人一定都满足 r * quality[i] > wage[i]（因为已经被选上了自然满足条件2）
4. 上式逆推为 r > (wage/quality),故我们将所有人按照 wage/quality 的大小排序，依次作为r 来判断最后的总价格。
5. 注意N,K都达到了10000，O(n^2)的方法显然不行（绝大部分情况下）

1. 按照wage/quality排序，若选定第i个人的比例r作为标准，那么还需从0到i-1中的人选k-1个人
2. 对于0到i-1个人，他们每个人的价格就是quality*r，r是固定的，所以quality越小越好，所以我们用最大堆将quality大的丢弃

    def mincostToHireWorkers(self, quality, wage, K):
        # 按比例排序,nlogn
        workers = sorted([float(wage[i])/quality[i], quality[i]] for i in range(len(quality)))
        res,qsum = float('inf'),0
        heap = []

        for i in range(len(workers)):
         # 选定比例 r
            r,q = workers[i]
            heapq.heappush(heap,-q)
            # qsum始终记录k个人的quality之和，乘以r即为最后结果
            qsum += q
            if len(heap) > K:
             # 始终丢弃quality最大的人
                qsum += heapq.heappop(heap)
            if len(heap) == K:
                res = min(res, qsum * r)
        return res

https://hinanawitenshi.github.io/2018/12/01/leetcode-857/

首先，对题目中的两个条件进行解读。

由题中第一个条件可知：

选定的K个人中，每人发放的实际工资pay与quality的比值相同。

定义价性比ratio = wage / quality，表达每个工人单位quality期望的工资，定义实际价性比ratio_ = pay / quality，那么由题中第二个条件可知：

选定的K个人中，每人发放的实际工资pay与quality的比值必须大于ratio。

综上所述，可得本题关键性的信息：

选定的K个人中，ratio_ >= max{ratio}，即实际价性比不得低于雇佣的工人中最高的期望价性比。

又因为总工资cost = ratio_ * sum(quality)，所以要使得总工资尽可能的小，就要使ratio_和sum(quality)尽可能小，因此可得具体的算法流程如下：

1. 对所有人按价性比进行排序。
2. 选择价性比最低的前K个人作为初始集，计算总工资。
3. 从第K + 1个人开始，循环如下过程直至无人可以添加：
   1. 踢出原集合中quality最大的工人，并添加该新工人。
   2. 重新计算quality的总和。
   3. 重新计算总工资，若小于当前最小值，则更新该值。

上述算法本质即遍历所有可能的价性比，找出最小的总工资。

枚举 nn 个人，每次枚举寻找最大值时间复杂度为常数，弹出质量最高的人并将第 ii 个人插入堆中的时间复杂度为 O(logK)O(log⁡K)，故总时间复杂度为 O(nlogK)O(nlog⁡K)。

https://segmentfault.com/a/1190000017235417

  public double mincostToHireWorkers(int[] quality, int[] wage, int K) {

    int n = quality.length;

    double[][] workers = new double[n][2];

    for (int i = 0; i < n; i++) {

      double ratio = (double) wage[i] / quality[i];

      workers[i] = new double[] { ratio, (double) quality[i] };

    }

    Arrays.sort(workers, (a, b) -> Double.compare(a[0], b[0]));

    PriorityQueue<Double> pq = new PriorityQueue<>((a, b) -> Double.compare(b, a));

    double res = Double.MAX_VALUE, totalQuality = 0;

    for (double[] worker : workers) {

      totalQuality += worker[1];

      pq.offer(worker[1]);

      if (pq.size() > K) {

        double maxQuality = pq.poll();

        totalQuality -= maxQuality;

      }

      if (pq.size() == K) {

        double currQ = worker[0];

        double curTotal = totalQuality * currQ;

        res = Math.min(res, curTotal);

      }

    }

    return res;

  }

http://hehejun.blogspot.com/2018/09/leetcodeminimum-cost-to-hire-k-workers.html

所以对于一个K个人的group，这K个人的总工资是取决于两项的：

1. K个人当中，wage/quality的比例最高的
2. K个人的总quality

那么我们可以对所有人按照wage/quality的比例从小到大排序。并且维护一个根据quality比较的max heap。这样当我们遍历到第i个人，他的wage/quality是目前为止最高的，所以其为决定整体工资的第一个因素(后面的元素我们不需要考虑，因为其wage/quality比例更大，放进去当前元素就无法决定最大比例了)。在这个条件下，如果heap中元素大于K个，我们把quality最高的踢掉一直到size为K，这样第二个因素可以控制到最小，那么两者相乘就是当前wage/quality比例下的K个人的最少工资。那么我们遍历完这所有的wage/quality比例，在所有最少工资中取最小的即可。时间复杂度O(N * log N)，代码如下：

    double mincostToHireWorkers(vector<int>& quality, vector<int>& wage, int K) {

        int len = quality.size();

        vector<int> idxs;

        for (int i = 0; i < len; ++i)idxs.push_back(i);

        auto comp = [&](const int& lhs, const int& rhs)

        {

            return getRatio(quality[lhs], wage[lhs]) < getRatio(quality[rhs], wage[rhs]);

        };

        sort(idxs.begin(), idxs.end(), comp);

        //find the lowest total quality for current ratio

        //we alwasy pick the largest ratio as the ratio

        //of current group since we need to meet the minimum

        //wage request for everyone

        priority_queue<int> pq;

        double res = 10e9;

        int totalQ = 0;

        for (const auto& idx : idxs)

        {

            double ratio = getRatio(quality[idx], wage[idx]);

            int currQ = quality[idx];

            if (pq.size() == K)

            {

                totalQ -= pq.top();

                pq.pop();

            }

            //bug: pop first then push, otherwise new pushed element might be popped out

            totalQ += currQ;

            pq.push(currQ);

            if (pq.size() == K)res = min(res, totalQ * ratio);

        }

        return res;

    } 

private:

    double getRatio(int q, int w)

    {

        return static_cast<double>(w) / static_cast<double>(q);

    }

https://leetcode.com/problems/minimum-cost-to-hire-k-workers/discuss/141768/Detailed-explanation-O(NlogN)

"1. Every worker in the paid group should be paid in the ratio of their quality compared to other workers in the paid group."
So for any two workers in the paid group,
we have wage[i] : wage[j] = quality[i] : quality[j]
So we have wage[i] : quality[i] = wage[j] : quality[j]
We pay wage to every worker in the group with the same ratio compared to his own quality.

"2. Every worker in the paid group must be paid at least their minimum wage expectation."
For every worker, he has an expected ratio of wage compared to his quality.

So to minimize the total wage, we want a small ratio.
So we sort all workers with their expected ratio, and pick up K first worker.
Now we have a minimum possible ratio for K worker and we their total quality.

As we pick up next worker with bigger ratio, we increase the ratio for whole group.
Meanwhile we remove a worker with highest quality so that we keep K workers in the group.
We calculate the current ratio * total quality = total wage for this group.

We redo the process and we can find the minimum total wage.
Because workers are sorted by ratio of wage/quality.
For every ratio, we find the minimum possible total quality of K workers.

Time Complexity
O(NlogN) for sort.
O(NlogK) for priority queue.

Question: "However, it is possible that current worker has the highest quality, so you removed his quality in the last step, which leads to the problem that you are "using his ratio without him".
Answer: It doesn't matter. The same group will be calculated earlier with smaller ratio.
And it doesn't obey my logic here: For a given ratio of wage/quality, find minimum total wage of K workers.

    public double mincostToHireWorkers(int[] q, int[] w, int K) {
        double[][] workers = new double[q.length][2];
        for (int i = 0; i < q.length; ++i)
            workers[i] = new double[]{(double)(w[i]) / q[i], (double)q[i]};
        Arrays.sort(workers, (a, b) -> Double.compare(a[0], b[0]));
        double res = Double.MAX_VALUE, qsum = 0;
        PriorityQueue<Double> pq = new PriorityQueue<>();
        for (double[] worker: workers) {
            qsum += worker[1];
            pq.add(-worker[1]);
            if (pq.size() > K) qsum += pq.poll();
            if (pq.size() == K) res = Math.min(res, qsum * worker[0]);
        }
        return res;
    }

Approach 2: Heap

As in Approach #1, at least one worker is paid their minimum wage expectation.

Additionally, every worker has some minimum ratio of dollars to quality that they demand. For example, if wage[0] = 100 and quality[0] = 20, then the ratio for worker 0 is 5.0.

The key insight is to iterate over the ratio. Let's say we hire workers with a ratio R or lower. Then, we would want to know the K workers with the lowest quality, and the sum of that quality. We can use a heap to maintain these variables.

Algorithm

Maintain a max heap of quality. (We're using a minheap, with negative values.) We'll also maintain sumq, the sum of this heap.

For each worker in order of ratio, we know all currently considered workers have lower ratio. (This worker will be the 'captain', as described in Approach #1.) We calculate the candidate answer as this ratio times the sum of the smallest K workers in quality.

• Time Complexity: $O(N \log N)$, where $N$ is the number of workers.
• Space Complexity: $O(N)$. 

  public double mincostToHireWorkers(int[] quality, int[] wage, int K) {

    int N = quality.length;

    Worker[] workers = new Worker[N];

    for (int i = 0; i < N; ++i)

      workers[i] = new Worker(quality[i], wage[i]);

    Arrays.sort(workers);

    double ans = 1e9;

    int sumq = 0;

    PriorityQueue<Integer> pool = new PriorityQueue();

    for (Worker worker : workers) {

      pool.offer(-worker.quality);

      sumq += worker.quality;

      if (pool.size() > K)

        sumq += pool.poll();

      if (pool.size() == K)

        ans = Math.min(ans, sumq * worker.ratio());

    }

    return ans;

  }

}

class Worker implements Comparable<Worker> {

  public int quality, wage;

  public Worker(int q, int w) {

    quality = q;

    wage = w;

  }

  public double ratio() {

    return (double) wage / quality;

  }

  public int compareTo(Worker other) {

    return Double.compare(ratio(), other.ratio());

  }

Approach 1: Greedy

At least one worker will be paid their minimum wage expectation. If not, we could scale all payments down by some factor and still keep everyone earning more than their wage expectation.

Algorithm

For each captain worker that will be paid their minimum wage expectation, let's calculate the cost of hiring K workers where each point of quality is worth wage[captain] / quality[captain] dollars. With this approach, the remaining implementation is straightforward.

Note that this algorithm would not be efficient enough to pass larger test cases.

• Time Complexity: $O(N^2 \log N)$, where $N$ is the number of workers.
• Space Complexity: $O(N)$. 

  public double mincostToHireWorkers(int[] quality, int[] wage, int K) {

    int N = quality.length;

    double ans = 1e9;

    for (int captain = 0; captain < N; ++captain) {

      // Must pay at least wage[captain] / quality[captain] per qual

      double factor = (double) wage[captain] / quality[captain];

      double prices[] = new double[N];

      int t = 0;

      for (int worker = 0; worker < N; ++worker) {

        double price = factor * quality[worker];

        if (price < wage[worker])

          continue;

        prices[t++] = price;

      }

      if (t < K)

        continue;

      Arrays.sort(prices, 0, t);

      double cand = 0;

      for (int i = 0; i < K; ++i)

        cand += prices[i];

      ans = Math.min(ans, cand);

    }

    return ans;

  }