1792: Maximum-Average-Pass-Ratio
Medium

table of contents

Your friendly neighbourhood Batman has NOT been slacking. Do NOT comment on last months performance. Anyways-

Intuitively speaking, the pseudocode for this algorithm is quite easy to come up with. For the extra students, you always want to place them into the class that will raise the pass rate the most. To do this efficiently, we can use a priority queue to keep track of the classes that would benefit the most from receiving an extra passing student.

Starting off, we define a bonus function which calculates how much an additional student contributes to the pass rate.

double bonus(int pass, int total) {
    return (double)(pass+1) / (total+1) - (double)pass / total;
}

Then, we define a max heap, and place all the values from classes into it:

priority_queue<pair<double, int>> pq;
for (int i = 0; i < classes.size(); ++i) {
    pq.emplace(bonus(classes[i][0], classes[i][1]), i);
}

Now, while there are still extraStudents left to place into classes, we pop the class that would benefit the most from receiving an extra passing student, place the student inside and emplace it back into the max heap:

while (extraStudents > 0) {
    pair<double, int> top = pq.top();
    pq.pop();
    ++classes[top.second][0];
    ++classes[top.second][1];
    pq.emplace(bonus(classes[top.second][0], classes[top.second][1]), top.second);
    --extraStudents;
}

Finally, to calculate the average pass ratio, we can simply re-iterate through all the classes, sum up their pass ratios and divide it by classes.size():

double ans = 0;
for (vector<int>& c : classes) {
    ans += (double)c[0]/c[1];
}

return ans / classes.size();

code

class Solution {
public:
    double maxAverageRatio(vector<vector<int>>& classes, int extraStudents) {
        priority_queue<pair<double, int>> pq;
        for (int i = 0; i < classes.size(); ++i) {
            pq.emplace(bonus(classes[i][0], classes[i][1]), i);
        }

        while (extraStudents > 0) {
            pair<double, int> top = pq.top();
            pq.pop();
            ++classes[top.second][0];
            ++classes[top.second][1];
            pq.emplace(bonus(classes[top.second][0], classes[top.second][1]), top.second);
            --extraStudents;
        }

        double ans = 0;
        for (vector<int>& c : classes) {
            ans += (double)c[0]/c[1];
        }

        return ans / classes.size();
    }
private:
    double bonus(int pass, int total) {
        return (double)(pass+1) / (total+1) - (double)pass / total;
    }
};

complexity

time taken