Skip to content

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<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;
  }
};

 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<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;
  }
}

 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