LeetCode Solutions
857. Minimum Cost to Hire K Workers
Time: $O(n\log n + n\log k)$ Space: $O(n)$
class Solution {
public:
double mincostToHireWorkers(vector<int>& quality, vector<int>& wage, int k) {
double ans = DBL_MAX;
int qualitySum = 0;
// (wagePerQuality, quality) sorted by wagePerQuality
vector<pair<double, int>> workers;
priority_queue<int> maxHeap;
for (int i = 0; i < quality.size(); ++i)
workers.emplace_back((double)wage[i] / quality[i], quality[i]);
sort(begin(workers), end(workers));
for (const auto& [wagePerQuality, q] : workers) {
maxHeap.push(q);
qualitySum += q;
if (maxHeap.size() > k)
qualitySum -= maxHeap.top(), maxHeap.pop();
if (maxHeap.size() == k)
ans = min(ans, qualitySum * wagePerQuality);
}
return ans;
}
};
class Solution {
public double mincostToHireWorkers(int[] quality, int[] wage, int k) {
double ans = Double.MAX_VALUE;
int qualitySum = 0;
// (wagePerQuality, quality) sorted by wagePerQuality
Pair<Double, Integer>[] workers = new Pair[quality.length];
Queue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);
for (int i = 0; i < quality.length; ++i)
workers[i] = new Pair<>((double) wage[i] / quality[i], quality[i]);
Arrays.sort(workers, (a, b) -> Double.compare(a.getKey(), b.getKey()));
for (Pair<Double, Integer> worker : workers) {
final double wagePerQuality = worker.getKey();
final int q = worker.getValue();
maxHeap.offer(q);
qualitySum += q;
if (maxHeap.size() > k)
qualitySum -= maxHeap.poll();
if (maxHeap.size() == k)
ans = Math.min(ans, qualitySum * wagePerQuality);
}
return ans;
}
}
class Solution:
def mincostToHireWorkers(self, quality: List[int], wage: List[int], k: int) -> float:
ans = math.inf
qualitySum = 0
# (wagePerQuality, quality) sorted by wagePerQuality
workers = sorted((w / q, q) for q, w in zip(quality, wage))
maxHeap = []
for wagePerQuality, q in workers:
heapq.heappush(maxHeap, -q)
qualitySum += q
if len(maxHeap) > k:
qualitySum += heapq.heappop(maxHeap)
if len(maxHeap) == k:
ans = min(ans, qualitySum * wagePerQuality)
return ans