857. Minimum Cost to Hire K Workers
Approach
Sort workers by wage-to-quality ratio; slide a max-heap window of size k on quality; track the minimum total cost.
Key Techniques
Array problems involve manipulating elements stored in a contiguous block of memory. Key techniques include two-pointer traversal, prefix sums, sliding windows, and in-place partitioning. In C#, arrays are zero-indexed and fixed in size — use List<T> when you need dynamic resizing.
Math problems test number theory, combinatorics, and modular arithmetic. Common tools: GCD/LCM (Euclidean algorithm), prime sieve, modular inverse (Fermat's little theorem), digit manipulation, and bit tricks. Overflow is a key concern in C# — use long when products may exceed 2³¹.
Greedy algorithms make locally optimal choices at each step, hoping to reach a global optimum. Greedy works when a problem has the "greedy choice property" and "optimal substructure". Common applications: interval scheduling, activity selection, Huffman coding, and jump game.
// Approach: Sort workers by wage-to-quality ratio; slide a max-heap window of size k on quality; track the minimum total cost.
// Time: O(n log n) Space: O(k)
public class Solution
{
public double MincostToHireWorkers(int[] quality, int[] wage, int k)
{
double ans = double.MaxValue;
int qualitySum = 0;
Tuple<double, int>[] workers = new Tuple<double, int>[quality.Length];
var pq = new PriorityQueue<int, int>(new CustomComparer());
for (int i = 0; i < quality.Length; i++)
workers[i] = Tuple.Create((double)wage[i] / quality[i], quality[i]);
Array.Sort(workers, (a, b) => a.Item1.CompareTo(b.Item1));
foreach (Tuple<double, int> worker in workers)
{
double wageperQuality = worker.Item1;
int q = worker.Item2;
pq.Enqueue(q, q);
qualitySum += q;
if (pq.Count > k)
qualitySum -= pq.Dequeue();
if (pq.Count == k)
ans = Math.Min(ans, qualitySum * wageperQuality);
}
return ans;
}
}
public class CustomComparer : IComparer<int>
{
public int Compare(int x, int y)
{
// Custom comparison logic
// For example, descending order
return y.CompareTo(x);
}
}