# Minimum Cost to Hire K Workers
**Difficulty:** HARD
[External](https://leetcode.com/problems/minimum-cost-to-hire-k-workers)
Canonical: https://scaleengineer.com/dsa/problems/minimum-cost-to-hire-k-workers
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Heap (Priority Queue)
---
## Problem
There are `n` workers. You are given two integer arrays `quality` and `wage` where `quality[i]` is the quality of the `ith` worker and `wage[i]` is the minimum wage expectation for the `ith` worker.

We want to hire exactly `k` workers to form a **paid group**. To hire a group of `k` workers, we must pay them according to the following rules:

1. Every worker in the paid group must be paid at least their minimum wage expectation.
2. In the group, each worker's pay must be directly proportional to their quality. This means if a worker’s quality is double that of another worker in the group, then they must be paid twice as much as the other worker.

Given the integer `k`, return _the least amount of money needed to form a paid group satisfying the above conditions_. Answers within `10-5` of the actual answer will be accepted.

**Example 1:**

**Input:** quality = [10,20,5], wage = [70,50,30], k = 2
**Output:** 105.00000
**Explanation:** We pay 70 to 0th worker and 35 to 2nd 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 0th worker, 13.33333 to 2nd and 3rd workers separately.

**Constraints:**

* `n == quality.length == wage.length`
* `1 <= k <= n <= 104`
* `1 <= quality[i], wage[i] <= 104`

# Approaches
## Brute Force by Generating All Combinations
The most straightforward approach is to exhaustively check every possible group of `k` workers. We can generate all combinations of `k` workers from the total pool of `n` workers. For each of these groups, we calculate the minimum cost required to hire them according to the rules and keep track of the overall minimum cost found.
**Time:** O(C(n, k) * k) - Where C(n, k) is the number of combinations, `n! / (k! * (n-k)!)`. This is exponential and grows extremely fast, making it impractical for the given constraints. · **Space:** O(k) - This is for storing the current combination and for the recursion stack depth.
**Pros:** Conceptually simple and easy to understand.; Guaranteed to find the correct answer.
**Cons:** Extremely inefficient due to the combinatorial explosion of possible groups.; Will result in a 'Time Limit Exceeded' error for all but the smallest input sizes.
### Explanation
For any given group of `k` workers, the payment structure must be fair and meet minimum expectations. The rule that pay is proportional to quality implies `paid_wage[i] = ratio * quality[i]` for some constant `ratio`. To meet the minimum wage `wage[i]`, we must have `ratio * quality[i] >= wage[i]`, which means `ratio >= wage[i] / quality[i]`. This must hold for all workers in the group. To minimize the total cost, which is `ratio * sum(qualities)`, we should choose the smallest possible `ratio`. Therefore, for a given group, `ratio = max(wage[i] / quality[i])` over all workers `i` in that group.

The brute-force algorithm iterates through every unique subset of `k` workers. For each subset, it computes this maximum ratio, sums up the qualities, calculates the total cost, and updates a global minimum. This process guarantees finding the optimal solution since it explores the entire search space.

```java
class Solution {
    double minCost = Double.MAX_VALUE;

    public double mincostToHireWorkers(int[] quality, int[] wage, int k) {
        int n = quality.length;
        findCombinations(0, new ArrayList<>(), quality, wage, k);
        return minCost;
    }

    private void findCombinations(int start, List<Integer> combination, int[] quality, int[] wage, int k) {
        if (combination.size() == k) {
            calculateCost(combination, quality, wage);
            return;
        }

        if (start >= quality.length) {
            return;
        }

        // Using a loop to generate combinations and avoid deep recursion for the same path
        for (int i = start; i < quality.length; i++) {
            combination.add(i);
            findCombinations(i + 1, combination, quality, wage, k);
            combination.remove(combination.size() - 1); // backtrack
        }
    }

    private void calculateCost(List<Integer> combination, int[] quality, int[] wage) {
        double maxRatio = 0.0;
        int sumQuality = 0;

        for (int i : combination) {
            maxRatio = Math.max(maxRatio, (double) wage[i] / quality[i]);
            sumQuality += quality[i];
        }

        minCost = Math.min(minCost, maxRatio * sumQuality);
    }
}
```
### Algorithm
*   Initialize `min_cost` to a very large number.
*   Generate all combinations of `k` workers from the `n` available workers. This can be done using a recursive backtracking function.
*   For each combination (a group of `k` workers):
    1.  Calculate the group's ratio `R`. This must be the maximum of `wage[i] / quality[i]` for all workers `i` in the group to satisfy everyone's minimum wage.
    2.  Calculate the sum of qualities, `S`, for all workers in the group.
    3.  The cost for this group is `C = R * S`.
    4.  Update `min_cost = min(min_cost, C)`.
*   After checking all combinations, `min_cost` will hold the result.

## Improved Brute Force by Iterating Through Captains
This approach is an improvement over the pure brute-force method. Instead of generating combinations, it iterates through each worker and considers them as the one who sets the wage-to-quality ratio for the group. This worker is called the 'captain'. The captain's ratio is the highest ratio in the group, and all other members must have a ratio less than or equal to the captain's.
**Time:** O(N^2 * log N) - The outer loop runs N times. Inside, we iterate N times to find eligible workers (O(N)) and then sort a list of up to N elements (O(N log N)). This makes the total complexity O(N * (N + N log N)) which simplifies to O(N^2 log N). · **Space:** O(N) - To store the list of qualities for eligible workers, which can be up to N in the worst case.
**Pros:** More efficient than the combinatorial brute-force approach.; Reduces the problem from exponential to polynomial time.
**Cons:** The time complexity of O(N^2 log N) is still too high for the given constraints (N up to 10^4).; Involves redundant computations, as for each captain, we rebuild and re-sort a list of eligible workers.
### Explanation
The logic hinges on the fact that for any optimal group of `k` workers, the group's wage-to-quality ratio will be determined by one of its members—the one with the highest `wage/quality` ratio. So, we can iterate through every worker, `i`, and hypothesize that they are this 'captain'.

For each potential captain `i`, we fix the group's ratio to `R_i = wage[i] / quality[i]`. Then, we find all other workers `j` who could be part of this group. A worker `j` is eligible if their own ratio `wage[j] / quality[j]` is not greater than `R_i`. From this pool of eligible workers (which includes the captain `i`), we must choose `k` workers. To minimize the total cost `R_i * sum(qualities)`, we must select the `k` eligible workers with the lowest qualities. 

We gather the qualities of all eligible workers, sort them, and take the sum of the smallest `k` qualities. This sum is then multiplied by `R_i` to get a potential minimum cost. We repeat this for all `n` possible captains and take the minimum of all calculated costs.

```java
import java.util.ArrayList; 
import java.util.Collections;
import java.util.List;

class Solution {
    public double mincostToHireWorkers(int[] quality, int[] wage, int k) {
        int n = quality.length;
        double minCost = Double.MAX_VALUE;

        for (int i = 0; i < n; i++) {
            double captainRatio = (double) wage[i] / quality[i];
            List<Integer> eligibleQualities = new ArrayList<>();

            for (int j = 0; j < n; j++) {
                if ((double) wage[j] / quality[j] <= captainRatio) {
                    eligibleQualities.add(quality[j]);
                }
            }

            if (eligibleQualities.size() < k) {
                continue;
            }

            Collections.sort(eligibleQualities);
            
            int qualitySum = 0;
            for (int l = 0; l < k; l++) {
                qualitySum += eligibleQualities.get(l);
            }

            minCost = Math.min(minCost, captainRatio * qualitySum);
        }

        return minCost;
    }
}
```
### Algorithm
*   Initialize `min_cost` to a very large number.
*   Iterate through each worker `i` from `0` to `n-1`, considering them as the 'captain' of the group.
*   For each potential captain `i`, the group's payment ratio is fixed at `captain_ratio = (double)wage[i] / quality[i]`.
*   Create a list of `eligible_qualities` for all workers `j` whose ratio `(double)wage[j] / quality[j]` is less than or equal to `captain_ratio`.
*   If the number of eligible workers is less than `k`, we cannot form a valid group, so we continue to the next captain.
*   If there are enough eligible workers, sort the `eligible_qualities` list.
*   To minimize cost, pick the `k` smallest qualities from the sorted list and sum them up (`sum_quality`).
*   Calculate the cost for this group: `current_cost = captain_ratio * sum_quality`.
*   Update `min_cost = min(min_cost, current_cost)`.
*   Return `min_cost` after checking all possible captains.

## Greedy Approach with Sorting and Max-Heap
The most efficient solution uses a greedy approach combined with a max-heap. The key idea is to process workers in increasing order of their wage-to-quality ratio. By doing this, whenever we consider a worker `i`, they have the highest ratio among all workers processed so far. This worker can act as the 'captain' for a group formed from the workers seen up to this point. We use a max-heap to efficiently maintain a group of `k` workers with the smallest sum of qualities.
**Time:** O(N log N) - Sorting the N workers takes O(N log N). The subsequent loop iterates N times, with each heap operation (offer/poll) taking O(log k) time. The total time for the loop is O(N log k). Therefore, the overall time complexity is O(N log N + N log k), which is dominated by the sorting step, resulting in O(N log N). · **Space:** O(N) - We need O(N) space to store the list of worker objects. The max-heap requires O(k) space. Thus, the total space complexity is O(N + k) = O(N).
**Pros:** Optimal and highly efficient, passing all test cases within the time limit.; Cleverly combines sorting and a priority queue to avoid re-computation.
**Cons:** The logic is more complex and less intuitive than the brute-force methods.; Requires understanding of greedy algorithms and priority queues.
### Explanation
First, we encapsulate each worker's data (`quality`, `wage`, and the calculated `ratio = wage/quality`) into an object. We then sort all workers based on their `ratio` in ascending order.

We iterate through this sorted list. As we process each worker, we add their quality to a max-heap. The max-heap's purpose is to keep track of the `k` smallest qualities encountered so far. If, after adding a new quality, the heap's size exceeds `k`, we remove the largest element (the top of the max-heap). This ensures the heap always contains the `k` workers with the lowest qualities among those considered.

Whenever the heap contains exactly `k` workers, we have a valid potential group. The workers in this group are those whose qualities are in the heap. Because we are iterating through workers sorted by ratio, the current worker has the highest ratio among this group. Therefore, this worker's ratio can be used as the ratio for the entire group. We calculate the cost for this group by multiplying the current worker's ratio by the sum of qualities in the heap. We keep track of the minimum cost found across all such valid groups.

This approach works because for any set of `k` workers, the cost is `max_ratio * sum_quality`. By sorting by ratio, we ensure that when we calculate a cost, the current worker's ratio is indeed the `max_ratio` for the group of `k` smallest-quality workers considered so far. The heap allows us to maintain this `sum_quality` efficiently.

```java
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.PriorityQueue;

class Solution {
    class Worker implements Comparable<Worker> {
        public int quality;
        public double ratio;

        public Worker(int quality, int wage) {
            this.quality = quality;
            this.ratio = (double) wage / quality;
        }

        @Override
        public int compareTo(Worker other) {
            return Double.compare(this.ratio, other.ratio);
        }
    }

    public double mincostToHireWorkers(int[] quality, int[] wage, int k) {
        int n = quality.length;
        List<Worker> workers = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            workers.add(new Worker(quality[i], wage[i]));
        }

        Collections.sort(workers);

        double minCost = Double.MAX_VALUE;
        int qualitySum = 0;
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

        for (Worker worker : workers) {
            qualitySum += worker.quality;
            maxHeap.offer(worker.quality);

            if (maxHeap.size() > k) {
                qualitySum -= maxHeap.poll();
            }

            if (maxHeap.size() == k) {
                minCost = Math.min(minCost, worker.ratio * qualitySum);
            }
        }

        return minCost;
    }
}
```
### Algorithm
*   Create a custom `Worker` class or object to store each worker's quality and their wage-to-quality ratio.
*   Create a list of these `Worker` objects for all `n` workers.
*   Sort this list of workers in ascending order based on their ratio.
*   Initialize `minCost` to infinity, `qualitySum` to 0, and a max-heap (a `PriorityQueue` in Java with a reverse order comparator).
*   Iterate through the ratio-sorted list of workers:
    1.  Add the current worker's quality to `qualitySum` and push it onto the max-heap.
    2.  If the heap's size becomes greater than `k`, it means we have more than `k` workers in our potential group. To keep only the `k` workers with the smallest qualities, we remove the largest quality from the heap (using `poll()`) and subtract it from `qualitySum`.
    3.  If the heap's size is exactly `k`, we have a valid group. The members of this group are the ones whose qualities are currently in the heap. The group's ratio is determined by the current worker (who has the highest ratio among all workers processed so far).
    4.  Calculate the cost for this group: `cost = current_worker.ratio * qualitySum`.
    5.  Update `minCost = min(minCost, cost)`.
*   After the loop finishes, `minCost` will hold the minimum cost.

# Solutions
### Java

```java
class Solution {
public
  double mincostToHireWorkers(int[] quality, int[] wage, int k) {
    int n = quality.length;
    Pair[] t = new Pair[n];
    for (int i = 0; i < n; ++i) {
      t[i] = new Pair(quality[i], wage[i]);
    }
    Arrays.sort(t, (a, b)->Double.compare(a.x, b.x));
    PriorityQueue<Integer> pq = new PriorityQueue<>((a, b)->b - a);
    double ans = 1 e9;
    int tot = 0;
    for (var e : t) {
      tot += e.q;
      pq.offer(e.q);
      if (pq.size() == k) {
        ans = Math.min(ans, tot * e.x);
        tot -= pq.poll();
      }
    }
    return ans;
  }
} class Pair {
  double x;
  int q;
  Pair(int q, int w) {
    this.q = q;
    this.x = (double)w / q;
  }
}

```

### CPP

```cpp
class Solution {
public:
  double mincostToHireWorkers(vector<int> &quality, vector<int> &wage, int k) {
    int n = quality.size();
    vector<pair<double, int>> t(n);
    for (int i = 0; i < n; ++i) {
      t[i] = {(double)wage[i] / quality[i], quality[i]};
    }
    sort(t.begin(), t.end());
    priority_queue<int> pq;
    double ans = 1e9;
    int tot = 0;
    for (auto &[x, q] : t) {
      tot += q;
      pq.push(q);
      if (pq.size() == k) {
        ans = min(ans, tot * x);
        tot -= pq.top();
        pq.pop();
      }
    }
    return ans;
  }
};

```

### Python

```python
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

```