> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Minimum Cost to Hire K Workers Python Solution

> Tested Python solution for LeetCode 857 with 15 pytest cases. Generate a practice environment with lcpy.

LeetCode 857, [Hard](/catalog/hard). Topics: [Array](/catalog/topics/array), [Greedy](/catalog/topics/greedy), [Sorting](/catalog/topics/sorting), [Heap (Priority Queue)](/catalog/topics/heap-priority-queue). [View on LeetCode](https://leetcode.com/problems/minimum-cost-to-hire-k-workers/description/).

Generate this problem as a practice environment: tested reference solution, 15 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 857   # by problem number
lcpy gen -s minimum_cost_to_hire_k_workers   # by problem name
```

## 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.*

### Examples

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

```
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 \<= 10^4
* 1 \<= quality\[i], wage\[i] \<= 10^4

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/minimum_cost_to_hire_k_workers/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/minimum_cost_to_hire_k_workers/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
import heapq


class Solution:
    # Time: O(n log n)
    # Space: O(n)
    def mincost_to_hire_workers(self, quality: list[int], wage: list[int], k: int) -> float:
        # Sort by wage/quality ratio; at ratio r the whole pool pays
        # r * total_quality, and lowest ratios keep the pool cheap
        workers = sorted(
            ((w / q, q) for q, w in zip(quality, wage, strict=True)),
            key=lambda x: x[0],
        )
        pool: list[int] = []  # negated qualities of the current k workers
        total_quality = 0
        best = float("inf")
        for ratio, q in workers:
            heapq.heappush(pool, -q)
            total_quality += q
            if len(pool) > k:
                total_quality += heapq.heappop(pool)
            if len(pool) == k:
                best = min(best, ratio * total_quality)
        return best
```

## Complexity

| Time | Space |
| - | - |
| O(n log n) | O(n) |

## Tags

[NeetCode All](/catalog/neetcode).


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.