C++ Greedy Max Heap O(m log n)
How much of profit in score can we get if we add one extra student to a particular class? Send an extra student to the class with the most profit; repeat till y
How much of profit in score can we get if we add one extra student to a particular class? Send an extra student to the class with the most profit; repeat till you run out of students.\n\nLet\'s track profits for all classes in a max heap. While we still have extra students, we pick a class that gives us the maximum profit, add a student, calculate new profit and put it back to the heap.\n\nTo avoid iterating through the max heap in the end, we can track the total score as we go.\n\n**C++**\n```cpp\ndouble maxAverageRatio(vector<vector<int>>& classes, int extraStudents) {\n    auto profit = [&](double pass, double total) {\n        return (pass + 1) / (total + 1) - pass / total;\n    };\n    double total = 0;\n    priority_queue<pair<double, array<int, 2>>> pq;\n    for (auto &c : classes) {\n        total += (double) c[0] / c[1];\n        pq.push({profit(c[0], c[1]), {c[0], c[1]}});\n    }\n    while (extraStudents--) {\n        auto [added_profit, c] = pq.top(); pq.pop();\n        total += added_profit;\n        pq.push({profit(c[0] + 1, c[1] + 1), {c[0] + 1, c[1] + 1}});\n    }\n    return total / classes.size();\n}\n```\n**Complexity Analysis**\n- Time: O(m log n), where n and m are the number of classes and extra students.\n\t- Caveat: the complexity for the code above is O((n + m) log n). To achieve O(m log n), we need construct the heap in O(n), e.g. by using `make_heap`.\n\t- For the purpose of complexity analsyis, I assume that we build the initial heap in O(n).\n- Memory: O(n) to hold the information about classes.\n
[]