A good way into this one is to ask: what do we need to remember so we never redo work blindly? For 857. Minimum Cost to Hire K Workers, the solution in this repository is mainly a heap / priority queue solution.
Guide
What?
The first job is to translate the English prompt into state, transition, and stopping conditions. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: heap / priority queue, greedy.
Guide
When?
This pattern shows up when the brute force version has too many repeated checks, too many possible branches, or too much bookkeeping to do by hand. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are mincostToHireWorkers.
Guide
Why?
The win comes from making each line carry responsibility: store the useful state, discard the rest, keep moving.
- Sorting is used to make local choices comparable, so the later scan does not have to rediscover order.
- The queue gives the solution a level-by-level or frontier-style traversal.
- The heap keeps the best candidate available without sorting the whole world every time.
- The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.
Guide
How?
Walk through the solution in this order:
- Read the setup variables first.
- Follow the main loop or recursive helper next.
- Watch where invalid states get skipped.
- Check which value survives to the return statement.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(NlogN), space: O(N)
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01//Runtime: 944 ms, faster than 6.75% of C++ online submissions for Minimum Cost to Hire K Workers.
02//Memory Usage: 10.3 MB, less than 100.00% of C++ online submissions for Minimum Cost to Hire K Workers.
03class Solution {
04public:
05 double mincostToHireWorkers(vector<int>& quality, vector<int>& wage, int K) {
06 vector<pair<int, int>> qws;
07 int N = quality.size();
08
09 for(int i = 0; i < N; i++){
10 qws.push_back(make_pair(quality[i], wage[i]));
11 }
12
13 //sort by wage/quality ratio, ascending
14 sort(qws.begin(), qws.end(),
15 [](const pair<int, int>& p1, const pair<int, int>& p2){
16 return (double)p1.second/p1.first < (double)p2.second/p2.first;
17 });
18
19 // for(int i = 0; i < N; i++){
20 // cout << qws[i].first << " " << qws[i].second << " " << (double)qws[i].second/qws[i].first << endl;
21 // }
22
23 //multiply the sum of quality with current wage/quality ratio
24 double ans = DBL_MAX;
25 double wqRatio;
26 vector<int> qualities;
27
28 for(int i = 0; i < N; i++){
29 pair<int, int> p = qws[i];
30 int q = p.first, w = p.second;
31 // cout << q << " " << w << endl;
32
33 //insert to right place so that we can access K smallest q(until now) quickly
34 auto it = upper_bound(qualities.begin(), qualities.end(), q);
35 if(it == qualities.end()){
36 qualities.push_back(q);
37 }else{
38 qualities.insert(it, q);
39 }
40
41 wqRatio = (double)w/q;
42 // cout << "wqRatio: " << wqRatio << endl;
43
44 if(i+1 >= K){
45 int qualitySum = accumulate(qualities.begin(), qualities.begin() + K, 0);
46 ans = min(ans, qualitySum * wqRatio);
47 }
48
49 }
50
51 return ans;
52 }
53};
54
55//Approach 2: Heap(My answer optimized with priority queue)
56//Runtime: 80 ms, faster than 17.64% of C++ online submissions for Minimum Cost to Hire K Workers.
57//Memory Usage: 9.9 MB, less than 100.00% of C++ online submissions for Minimum Cost to Hire K Workers.
58//time: O(NlogN), space: O(N)
59class Solution {
60public:
61 double mincostToHireWorkers(vector<int>& quality, vector<int>& wage, int K) {
62 vector<pair<int, int>> qws;
63 int N = quality.size();
64
65 for(int i = 0; i < N; i++){
66 qws.push_back(make_pair(quality[i], wage[i]));
67 }
68
69 //sort by wage/quality ratio, ascending
70 sort(qws.begin(), qws.end(),
71 [](const pair<int, int>& p1, const pair<int, int>& p2){
72 return (double)p1.second/p1.first < (double)p2.second/p2.first;
73 });
74
75 // for(int i = 0; i < N; i++){
76 // cout << qws[i].first << " " << qws[i].second << " " << (double)qws[i].second/qws[i].first << endl;
77 // }
78
79 //multiply the sum of quality with current wage/quality ratio
80 double ans = DBL_MAX;
81 double wqRatio;
82 vector<int> qualities;
83 //the greater the earlier to be popped
84 priority_queue<int, vector<int>, less<int>> pq;
85 int qualitySum = 0;
86
87 for(int i = 0; i < N; i++){
88 pair<int, int> p = qws[i];
89 int q = p.first, w = p.second;
90 // cout << q << " " << w << endl;
91 wqRatio = (double)w/q;
92 // cout << "wqRatio: " << wqRatio << endl;
93
94 pq.push(q);
95 qualitySum += q;
96
97 if(pq.size() > K){
98 int popped = pq.top(); pq.pop();
99 qualitySum -= popped;
100 }
101
102 if(i+1 >= K){
103 ans = min(ans, qualitySum * wqRatio);
104 }
105
106 }
107
108 return ans;
109 }
110};
111
112//Approach 1: Greedy
113//TLE
114//41 / 46 test cases passed.
115//time: O(N^2logN), space: O(N)
116class Solution {
117public:
118 double mincostToHireWorkers(vector<int>& quality, vector<int>& wage, int K) {
119 int N = quality.size();
120 double ans = DBL_MAX;
121
122 for(int captin = 0; captin < N; captin++){
123 double factor = (double)wage[captin]/quality[captin];
124 vector<double> prices; //the price of workers whose wq ratio above factor
125 for(int worker = 0; worker < N; worker++){
126 double price = factor * quality[worker];
127 if(price >= wage[worker]){
128 prices.push_back(price);
129 }
130 }
131
132 if(prices.size() < K) continue;
133
134 sort(prices.begin(), prices.end());
135 ans = min(ans, accumulate(prices.begin(), prices.begin()+K, 0.0));
136 }
137
138 return ans;
139 }
140};Cost
Complexity
Time
O(NlogN), space: O(N)
Dominated by the main traversal, recursion, or data-structure operations in the code.
Space
O(n) in the usual case for auxiliary containers or recursion
Auxiliary state plus the answer structure where the problem requires one.