Hiring and queues

Questions 1 to 5 of 8

1. 1. The lesson's min_cost_to_hire sorts the n workers once, then makes one pass where each step does a heap push and at most one heap pop. Which running time does the lesson give for the whole method?

   O(n^2)O(n log n)O(2^n)O(n^3)
2. 2. Why does the lesson's heap hold plain int qualities instead of whole Worker values?

   Because the heap must sort the workers by wage, and an int has no wageBecause a heap of workers would keep the lowest ratio on top, which is the wrong endBecause std::priority_queue<Worker> needs an operator< on Worker, and the lesson's struct does not define one, so the code does not compileBecause the heap must hold the largest ratio, and ints can store ratios exactly
3. 3. Put the steps of the method in the order the program runs them. Each step applies to the workers in ratio order.

   Use the arrows to put the steps in order.

   1. 1.If the heap holds more than k items, remove the top and subtract it from the sum↑↓
   2. 2.If the heap holds exactly k items, keep the smaller of the best cost and this ratio times the sum↑↓
   3. 3.Push the worker's quality into the max heap and add it to the running sum↑↓
   4. 4.Sort the workers by ratio, from smallest to largest↑↓
4. 4. What does this program print? ``cpp #include <algorithm> #include <iostream> #include <queue> #include <vector> struct Worker { int quality; int wage; double ratio() const { return static_cast<double>(wage) / quality; } }; int main() { std::vector<Worker> workers = {{20, 50}, {5, 30}, {10, 70}}; std::sort(workers.begin(), workers.end(), [](const Worker& a, const Worker& b) { return a.ratio() < b.ratio(); }); std::priority_queue<int> heap; long long sum = 0; for (const Worker& w : workers) { heap.push(w.quality); sum += w.quality; if (heap.size() > 2) { sum -= heap.top(); heap.pop(); } std::cout << "sum " << sum << ", heap " << heap.size() << '\n'; } } ``

   sum 20, heap 1; sum 25, heap 2; sum 15, heap 2sum 20, heap 1; sum 25, heap 2; sum 35, heap 3sum 20, heap 1; sum 25, heap 2; sum 25, heap 2sum 20, heap 1; sum 30, heap 2; sum 15, heap 2
5. 5. Brute force in the lesson tries every group of k workers. With 30 workers and k = 15, about how many groups does it check?

   about 30,000exactly 450about 155 millionabout 2 billion