# 857. Minimum Cost to Hire K Workers      • Time: $O(n\log n + n\log k)$
• Space: $O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 class Solution { public: double mincostToHireWorkers(vector& quality, vector& wage, int k) { double ans = DBL_MAX; int qualitySum = 0; // (wagePerQuality, quality) sorted by wagePerQuality vector> workers; priority_queue 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; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 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[] workers = new Pair[quality.length]; Queue 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 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; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 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