Minimum Cost To Hire K Workers - Leetcode Solution

The "Minimum Cost to Hire K Workers" problem on Leetcode is a problem that provides a set of workers, each with their own respective hourly wage and a specified number of hours they can work. The goal is to hire k workers so that the total cost of hiring them is minimized, with the constraint that each worker must be paid their specified hourly wage.

To solve this problem, we can first sort the workers based on their hourly rate in ascending order. Then, we can iterate through each worker, maintaining a priority queue of up to k workers with the largest hourly rate. The priority queue should contain tuples of (hourly rate, hours worked) for each worker.

As we iterate through each worker, we add them to the priority queue if it has less than k elements. If it has k elements, we compute the total cost of hiring these k workers by finding the sum of their hourly rate multiplied by the total hours worked. If this cost is less than our current minimum cost, we update our minimum cost.

We continue iterating through the remaining workers and updating our minimum cost until all workers have been processed.

Below is a detailed solution in Python:

import heapq

def mincostToHireWorkers(quality, wage, k):
    ratio = [float(w) / q for w, q in zip(wage, quality)]
    # sort workers by increasing hourly ratio
    workers = sorted(zip(ratio, quality))
    # initialize variables
    total_quality, min_cost = 0, float('inf')
    heap = []
    
    for r, q in workers:
        # add worker to priority queue if it hasn't reached k yet
        heapq.heappush(heap, -q)
        total_quality += q
        
        # remove worker with largest quality if heap is full
        if len(heap) > k:
            total_quality += heapq.heappop(heap)  # remove worker with highest quality
        
        # calculate cost if k workers have been selected
        if len(heap) == k:
            min_cost = min(min_cost, total_quality * r)
    
    return min_cost

The time complexity of this solution is O(n log n), where n is the number of workers. The space complexity is O(n), for storing the sorted workers and the priority queue.

1