{x}
blog image

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

Solution Explanation:

This problem asks to find the minimum cost to hire k workers, given their qualities and minimum wage expectations. The constraint is that the pay must be proportional to the quality within the group. This suggests an optimization problem that can be solved efficiently using a greedy approach combined with a priority queue (heap).

Core Idea:

The key observation is that for any worker, the ratio of their wage to their quality (wage[i] / quality[i]) represents the unit cost per quality point. The optimal solution involves selecting workers with the lowest unit cost, up to k workers. However, simply choosing the k lowest unit costs doesn't guarantee the minimum total cost because the total payment depends on the highest ratio among the selected workers.

Algorithm:

  1. Calculate Unit Costs and Sort: For each worker, compute wage[i] / quality[i] (let's call this ratio). Sort the workers based on these ratios in ascending order. This prioritizes workers with lower unit costs.

  2. Iterative Selection with Priority Queue:

    • Initialize a priority queue (pq) to store the qualities of the selected workers. This will help maintain the k highest quality workers.
    • Initialize total_quality to 0 and min_cost to a large value (infinity).
    • Iterate through the sorted workers:
      • Add the current worker's quality to total_quality.
      • Push the current worker's quality onto the priority queue.
      • If the priority queue size exceeds k, pop the highest quality worker (and subtract its quality from total_quality).
      • If the priority queue size equals k, calculate the total cost using the highest ratio (max_ratio) among the selected workers. total_cost = total_quality * max_ratio. Update min_cost if a lower cost is found.

  3. Return Minimum Cost: The min_cost after iterating through all workers represents the minimum cost to hire k workers.

Time Complexity Analysis:

  • Sorting the workers takes O(N log N) time, where N is the number of workers.
  • Iterating through the sorted workers takes O(N) time.
  • Priority queue operations (push and pop) take O(log k) time each. Since these operations are performed at most N times, the total time for priority queue operations is O(N log k).
  • Therefore, the overall time complexity is dominated by sorting, resulting in O(N log N). If k is significantly smaller than N, the complexity could be approximated to O(N log k).

Space Complexity Analysis:

The space complexity is O(N) for storing the sorted worker data and O(k) for the priority queue. In most cases, k is much smaller than N, so space complexity is essentially O(N).

Code Explanation (Python):

The Python code directly implements the algorithm described above. The heapq module provides the priority queue functionality. The lambda function in sorted() is used for sorting by the ratio. The code efficiently calculates and updates the minimum cost during iteration.

Code Explanation (Java, C++, Go):

The Java, C++, and Go code implement the same algorithm. The key differences are in the syntax and data structures used. Java and C++ use built-in priority queues (PriorityQueue and priority_queue). Go uses a custom heap implementation to simulate a priority queue. The logic remains consistent across all languages.