857. Minimum Cost to Hire K Workers

[mah-shamim]

Topics: Array, Greedy, Sorting, Heap (Priority Queue)

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 0^th worker and 35 to 2^nd 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 0^th worker, 13.33333 to 2^nd and 3^rd workers separately.

Example 3:

• Input: quality = [4,4,4,5], wage = [13,12,13,12], k = 2
• Output: 26.00000

Constraints:

• n == quality.length == wage.length
• 1 <= k <= n <= 104
• 1 <= quality[i], wage[i] <= 104

[basharul-siddike]

We need to hire exactly k workers while ensuring two conditions:

1. Each worker is paid at least their minimum wage.
2. The pay is proportional to the worker's quality.

Key Insights:

1. Ratio of Wage to Quality: The ratio wage[i] / quality[i] defines the minimum acceptable payment rate per unit of quality for worker i. If we decide to hire a worker at this ratio, every other worker in the group must be paid according to this ratio.
2. Greedy Approach: To minimize the total cost, we must ensure that the payment is based on the smallest possible wage-to-quality ratio for the group of workers.

Steps:

1. Sort by wage-to-quality ratio: We first sort the workers by their wage[i] / quality[i] ratio.
2. Use a Max-Heap for Quality: As we iterate through the workers in increasing order of the wage-to-quality ratio, we maintain a group of exactly k workers. To ensure the total quality is minimized, we use a max-heap to keep track of the largest quality workers. If we encounter a worker with higher quality than one already in the heap, we remove the largest quality worker (since that would increase the total cost).
3. Calculate the Total Cost: For each valid group of k workers, we compute the total cost as the sum of the qualities of the k workers multiplied by the current wage-to-quality ratio.

Let's implement this solution in PHP: 857. Minimum Cost to Hire K Workers

<?php
/**
 * @param Integer[] $quality
 * @param Integer[] $wage
 * @param Integer $k
 * @return Float
 */
function mincostToHireWorkers(array $quality, array $wage, int $k): float
{
    $n = count($quality);
    $workers = array();
    $ans = PHP_INT_MAX;
    $qualitySum = 0;

    // (wagePerQuality, quality) sorted by wagePerQuality
    for ($i = 0; $i < $n; ++$i) {
        $workers[$i] = array((double) $wage[$i] / $quality[$i], $quality[$i]);
    }

    // Sort by wagePerQuality ratio
    usort($workers, function($a, $b) {
        return $a[0] <=> $b[0];
    });

    // MaxHeap to keep track of largest quality workers
    $maxHeap = new SplMaxHeap();

    foreach ($workers as $worker) {
        $wagePerQuality = $worker[0];
        $q = $worker[1];
        $qualitySum += $q;
        $maxHeap->insert($q);

        // Ensure the heap contains at most 'k' workers
        if ($maxHeap->count() > $k) {
            // Remove the worker with the largest quality
            $qualitySum -= $maxHeap->extract();
        }

        // If we have exactly 'k' workers, calculate the cost
        if ($maxHeap->count() == $k) {
            // Total cost is (total quality of 'k' workers) * (current wagePerQuality)
            $ans = min($ans, $qualitySum * $wagePerQuality);
        }
    }

    return $ans;
}

// Example 1
$quality1 = [10, 20, 5];
$wage1 = [70, 50, 30];
$k1 = 2;
echo mincostToHireWorkers($quality1, $wage1, $k1) . "\n";  // Output: 105.00000

// Example 2
$quality2 = [3, 1, 10, 10, 1];
$wage2 = [4, 8, 2, 2, 7];
$k2 = 3;
echo mincostToHireWorkers($quality2, $wage2, $k2) . "\n";  // Output: 30.66667

// Example 3
$quality3 = [4, 4, 4, 5];
$wage3 = [13, 12, 13, 12];
$k3 = 2;
echo mincostToHireWorkers($quality3, $wage3, $k3) . "\n";  // Output: 26.00000
?>

Explanation:

1. Sorting: First, we calculate the wage/quality ratio for each worker and sort them in ascending order. This allows us to consider groups with the smallest wage-to-quality ratio first.

2. Heap Maintenance: We maintain a max-heap (using PHP's SplMaxHeap) to track the highest quality workers in our group of size k. If adding a new worker causes the heap to have more than k workers, we remove the one with the highest quality, as it would contribute more to the overall cost.

3. Cost Calculation: For each valid group of k workers, we calculate the total wage as qualitySum * wagePerQuality. The minimum wage is updated with each new group of k workers.

Example Walkthrough:

Example 1:

• Input: quality = [10, 20, 5], wage = [70, 50, 30], k = 2
• Step 1: Calculate the wage/quality ratio for each worker:
  • Worker 0: 70/10 = 7
  • Worker 1: 50/20 = 2.5
  • Worker 2: 30/5 = 6
• Step 2: Sort workers by ratio: [(2.5, 20), (6, 5), (7, 10)]
• Step 3: Use a max-heap to track the top k=2 workers. The final cost is 105.

Example 2:

• Input: quality = [3, 1, 10, 10, 1], wage = [4, 8, 2, 2, 7], k = 3
• Step 1: Calculate the wage/quality ratio:
  • Worker 0: 4/3 ≈ 1.33
  • Worker 1: 8/1 = 8
  • Worker 2: 2/10 = 0.2
  • Worker 3: 2/10 = 0.2
  • Worker 4: 7/1 = 7
• Step 2: Sort workers: [(0.2, 10), (0.2, 10), (1.33, 3), (7, 1), (8, 1)]
• Step 3: The final cost for k=3 is 30.66667.

Time Complexity:

• Sorting the workers takes O(n log n).
• Inserting and removing from the heap takes O(log k).
• The overall complexity is O(n log n), which is efficient given the constraints (n <= 10^4).

This solution ensures that the least amount of money is paid while maintaining fairness and proportionality based on worker quality.

[mah-shamim]

Thanks to solve the Minimum Cost to Hire K Workers problem

[basharul-siddike]

Thanks