We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Cost to Hire K Workers

Number: 887

Difficulty: Hard

Paid? No

Companies: Amazon, Meta, Google, Microsoft

Problem Description

Given a list of workers where each worker has a quality and a minimum wage expectation, the goal is to hire exactly k workers such that:

  • Every hired worker is paid at least their minimum wage.
  • All workers are paid in the same ratio (i.e. payment is proportional to quality). Find the minimum total cost to form such a group.

Key Insights

  • Determine the wage-to-quality ratio for each worker, which represents the minimum acceptable rate per unit quality.
  • By sorting workers by their ratio, you can ensure that if a worker is the highest ratio in the chosen group, then paying every worker according to this ratio meets the minimum wage requirement.
  • Use a max-heap (priority queue) to maintain the smallest total quality sum among the chosen workers. If the group exceeds size k, remove the worker with the highest quality (thus the highest contribution to cost) to minimize the total cost.
  • At each step (when heap size reaches k), compute the total cost as the current sum of qualities multiplied by the current worker’s ratio and update the minimum cost answer.

Space and Time Complexity

Time Complexity: O(n log n + n log k) Space Complexity: O(n)

Solution

This solution calculates the effective wage-to-quality ratio for each worker and sorts the workers by this ratio. The sorted order guarantees that any chosen group has a maximum ratio that enforces the proportional payment rule without violating any minimal wage constraints.

A max-heap is then used to keep track of the largest qualities among the selected workers. As we traverse through the sorted list, we add each worker's quality into the heap and update a running sum of qualities. If the heap size exceeds k, we remove the worker with the highest quality to keep only the k smallest qualities (thus minimizing cost). The current total cost candidate is then computed as the running sum multiplied by the current worker's ratio. The minimum such candidate is the solution.

The key data structures used are:

  • Array for storing worker data (ratios and quality).
  • Sorting algorithm to order workers by the computed ratio.
  • Max-heap (implemented using a min-heap of negative values in languages like Python) to efficiently maintain the current group’s total quality.

Code Solutions

# Python solution using heapq as a max-heap by pushing negative values.
import heapq

def mincostToHireWorkers(quality, wage, k):
    # Create a list of tuples (ratio, quality) for each worker.
    workers = []
    for q, w in zip(quality, wage):
        ratio = w / q  # Minimum acceptable wage per unit quality.
        workers.append((ratio, q))
    
    # Sort workers by their ratio in ascending order.
    workers.sort(key=lambda x: x[0])
    
    quality_sum = 0  # The running sum of qualities in the current group.
    max_quality_heap = []  # Max-heap to maintain the largest quality values (using negatives).
    min_cost = float('inf')  # Initialize the minimum cost as infinity.
    
    # Process each worker in order of increasing ratio.
    for ratio, q in workers:
        # Add the current worker's quality to the heap (invert sign for max-heap simulation).
        heapq.heappush(max_quality_heap, -q)
        quality_sum += q
        
        # If we have more than k workers, remove the one with the highest quality.
        if len(max_quality_heap) > k:
            removed_quality = -heapq.heappop(max_quality_heap)
            quality_sum -= removed_quality
        
        # When the group size is exactly k, calculate the cost.
        if len(max_quality_heap) == k:
            current_cost = quality_sum * ratio
            min_cost = min(min_cost, current_cost)
    
    return min_cost

# Example usage:
# quality = [10,20,5]
# wage = [70,50,30]
# k = 2
# Expected output: 105.00000
#print(mincostToHireWorkers([10,20,5], [70,50,30], 2))
← Back to All Questions