## Description

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

There are `n`

workers. You are given two integer arrays `quality`

and `wage`

where `quality[i]`

is the quality of the `i`

worker and ^{th}`wage[i]`

is the minimum wage expectation for the `i`

worker.^{th}

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:

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

Given the integer `k`

, return *the least amount of money needed to form a paid group satisfying the above conditions*. Answers within `10`

of the actual answer will be accepted.^{-5}

**Example 1:**

Input:quality = [10,20,5], wage = [70,50,30], k = 2Output:105.00000Explanation:We pay 70 to 0^{th}worker and 35 to 2^{nd}worker.

**Example 2:**

Input:quality = [3,1,10,10,1], wage = [4,8,2,2,7], k = 3Output:30.66667Explanation:We pay 4 to 0^{th}worker, 13.33333 to 2^{nd}and 3^{rd}workers separately.

**Constraints:**

`n == quality.length == wage.length`

`1 <= k <= n <= 10`

^{4}`1 <= quality[i], wage[i] <= 10`

^{4}

## Explanation

Use a heap to find worker qualities from high to low.

To find k workers is to find k workers with .

## Python Solution

```
class Solution:
def mincostToHireWorkers(self, quality: List[int], wage: List[int], k: int) -> float:
workers = []
for w,q in zip(wage, quality):
workers.append((w/q, w, q))
workers = sorted(workers)
heap = []
min_cost = sys.maxsize
quality_sum = 0
for ratio, wage, quality in workers:
heapq.heappush(heap, -quality)
quality_sum += quality
if len(heap) > k:
quality_sum += heapq.heappop(heap)
if len(heap) == k:
min_cost = min(min_cost, ratio * quality_sum)
return min_cost
```

- Time Complexity: O(N log (N))
- Space Complexity: O(N)