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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum Cost to Hire K Workers

Difficulty: Hard

Problem Description

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.

Key Insights

  • Each worker's pay is determined by the ratio of their wage to quality, which defines the minimum wage per unit quality.
  • Sorting workers based on the ratio of wage to quality helps in identifying the optimal group of k workers.
  • A priority queue (or min-heap) can efficiently keep track of the k workers with the highest quality while maintaining the minimum cost.

Space and Time Complexity

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

Solution

To solve the problem, we can follow these steps:

  1. Calculate the wage-to-quality ratio for each worker and sort the workers based on this ratio.
  2. Use a min-heap to maintain the k workers with the highest quality while iterating through the sorted list.
  3. For each worker processed, calculate the total cost based on the current wage-to-quality ratio, which determines the payment for all workers in the heap.
  4. Track the minimum cost encountered during this process.

Code Solutions

import heapq

def mincostToHireWorkers(quality, wage, k):
    # Create a list of workers with their quality and wage ratio
    workers = [(w/q, q) for w, q in zip(wage, quality)]
    # Sort workers by their wage-to-quality ratio
    workers.sort()
    
    # Min-heap to keep track of the top k qualities
    heap = []
    total_quality = 0
    min_cost = float('inf')
    
    for ratio, q in workers:
        # Add current worker's quality to the total quality
        heapq.heappush(heap, q)
        total_quality += q
        
        # Once we have more than k workers, remove the one with the lowest quality
        if len(heap) > k:
            total_quality -= heapq.heappop(heap)
        
        # If we have exactly k workers, calculate the cost
        if len(heap) == k:
            min_cost = min(min_cost, total_quality * ratio)
    
    return min_cost
← Back to All Questions