Sponsored
This approach uses a heap to dynamically maintain workers while iterating over them sorted by wage-to-quality ratio. The goal is to keep the sum of qualities of the selected workers minimal while ensuring all conditions are satisfied. We sort all workers by their wage-to-quality ratio because for each worker, to satisfy both their minimum wage and relative payment constraints, each selected worker must be paid at least this ratio times their quality.
Time Complexity: O(n log n) due to sorting, and O(n log k) for heap operations.
Space Complexity: O(n) for the sorted list of workers or the heap.
1#include <vector>
2#include <queue>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8public:
9 double mincostToHireWorkers(vector<int>& quality, vector<int>& wage, int k) {
10 vector<pair<double, int>> workers;
11 for (int i = 0; i < quality.size(); ++i) {
12 workers.emplace_back((double) wage[i] / quality[i], quality[i]);
13 }
14 sort(workers.begin(), workers.end());
15
16 priority_queue<int> max_heap;
17 int quality_sum = 0;
18 double result = 1e9;
19 for (const auto& [ratio, q] : workers) {
20 max_heap.push(q);
21 quality_sum += q;
22
23 if (max_heap.size() > k) {
24 quality_sum -= max_heap.top();
25 max_heap.pop();
26 }
27
28 if (max_heap.size() == k) {
29 result = min(result, ratio * quality_sum);
30 }
31 }
32
33 return result;
34 }
35};This C++ solution sorts workers based on their wage-to-quality ratio and employs a max-heap to maintain k workers with the lowest quality sum. As the sorted workers are processed, the heap stores the largest qualities such that when it exceeds k, the largest quality is removed to ensure efficiencies. The computed cost is determined by the current sum of qualities multiplied by the worker's ratio currently being assessed, minimizing the cost when necessary.
This approach focuses on sorting workers by the ratio of their wage expectation to quality. By calculating this ratio, we can use it as a reference point to determine the required payment for every possible group of k workers. Selecting the right workers and calculating the minimum payment by understanding proportional wages can be done by iterating over sorted worker lists using two indices, capturing the required details and performing the necessary calculations.
Time Complexity: O(n log n) due to sorting, and O(n log n) due to managing heap.
Space Complexity: O(n) for worker list and heap storage.
Here, the Python code sorts workers by their ratio of wage to quality. A max-heap manages the quality selection, and when a potential solution with k workers is found, the resultant cost is calculated. The approach makes efficient use of sorted ratios and quality management to derive the answer.