Problem Statement

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:

Every worker in the paid group must be paid at least their minimum wage expectation.
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

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 <= 10<sup>4</sup>
1 <= quality[i], wage[i] <= 10<sup>4</sup>

Intuition

In this problem we need to find the most effective workers. This means that workers with the best wage/quality ratio, while making sure we don't break the bank. This is a difficult question to understand but an easy one to implement. In order to solve this we will use a MaxHeap. Let's try to understand what we can do and how we can do it:

Prioritizing Efficiency: Sort the workers based on their "wage-to-quality ratio" . This means workers with lower wage demands relative to their skills are prioritized. The lower the ratio, the more efficient (cheaper for their skill level) the worker.
Keeping Track of Skills: We use a special data structure called a "max heap" to remember the skills (quality) of the k workers you've hired so far. This heap keeps the k workers with the LOWEST skills at the top, for easy access.
Building Our Team: We iterate through the sorted list of workers:
- For each worker:
  - We add their skill level (quality) to the heap.
  - We update the total skill level of our hired workers.
  - If we've already hired k workers (heap is full), we remove the worker with the LOWEST skill level from the heap (the one at the top) to make space for the new one. This ensures we consider replacing a less skilled worker with a potentially better option.
Calculating the Cost: Once we have k workers:
- We calculate the total cost by multiplying the total skill level of our team by the wage-to-quality ratio of the current worker being considered.
- We compare this cost with the overall minimum cost we've found so far. If it's lower, we update the minimum cost.
Finding the Best Deal: After considering all workers, the code returns the minimum total cost we'd pay to hire k workers with the best combination of skills and wage demands.

Lets checkout the code for above approach.

Code Solution

Python Code:

class Solution:
    def mincostToHireWorkers(self, quality: List[int], wage: List[int], k: int) -> float:
        # make a list of tuples with wage to quality ratio as 0th index
        # and quality as 1st index
        # this list will be sorted in ascending
        ratio = sorted([(w / q, q) for w, q in zip(wage, quality)])
        # initialize the heap
        max_heap = []
        # total sum of quality
        quality_sum = 0
        # max_ratio of wage to quality
        max_ratio = 0.0

        # iterate over a range of k
        for i in range(k):
            # max_ratio will be max of current max_ratio 
            # and current index's 0th position in ratio list
            max_ratio = max(max_ratio, ratio[i][0])
            # increase the total sum of quality
            quality_sum += ratio[i][1]
            # push the quality of curent index from ratio list
            heapq.heappush(max_heap, -ratio[i][1])
        # final cost after pushing first k workers to heap
        res = max_ratio * quality_sum
        # iterate from k to length of array range
        for i in range(k, len(quality)):
            # calculate max_Ratio again
            max_ratio = max(max_ratio, ratio[i][0])
            # quality_sum now becomes quality of current + lowest quality we have already chosen
            quality_sum += ratio[i][1] + heapq.heappop(max_heap)
            # push currrent quality to heap
            heapq.heappush(max_heap, -ratio[i][1])
            # res will be minimum of current res and max_ratio*quality_sum
            # that we have found till now
            res = min(res, max_ratio * quality_sum)
        # return the final cost to hire
        return res

Time and Space Complexity

Time Complexity:

$$O(n\ logn)$$

As we are using a heap and iterating over the array.

Space Complexity:

$$O(n)$$

As we're using a heap to store quality.

Conclusion

In this problem we get to learn how to use heap to solve this problem.

Hope that explanation made sense and you found this blog helpful. If you've made it this far, please give it a like and drop a comment.

Happy Coding!🚀

857. Minimum Cost to Hire K Workers

11th May 2024 LeetCode daily

Table of contents