📊 Max Average Ratio | 🚀 Greedy + Priority Queue Solution 💡
IntuitionThe problem asks for maximizing the average passing ratio after distributing extra students to various classes. Each class has a passing-to-total ratio
# Intuition\nThe problem asks for maximizing the average passing ratio after distributing extra students to various classes. Each class has a passing-to-total ratio, and by adding a student to the class with the most potential improvement in its ratio, we can maximize the overall average.\n\n---\n\n\n\n# Approach\nWe first calculate the initial average passing ratio for each class and store the potential improvement (calculated using the difference between the new and old ratios when adding a student). This potential improvement is stored in a priority queue (max-heap), where classes with the highest improvement come first. For each extra student, we pop the class with the highest potential improvement, increment its pass count and total, update the sum, and push the class back into the priority queue. This process continues until all extra students are assigned. Finally, the total sum is averaged by the number of classes.\n\n\n\n---\n\n\n\n# Complexity\n- Time complexity:\n$$O(n log n + m log n)$$\n\n- Space complexity:\n$$O(n)$$\n\n---\n\n\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    double calcAverage(int pass, int total){\n        return (double)(pass+1)/(total+1) - (double)pass/total;\n    }\n\n    double maxAverageRatio(vector<vector<int>>& classes, int extraStudents) {\n        if(!classes.size()) return 0;\n        priority_queue<pair<double,pair<int,int>>> pq;\n        double sum = 0.0;\n        for(auto x : classes){\n            int pass = x[0];\n            int total = x[1];\n            sum += (double)pass/total;\n            pq.push({calcAverage(pass,total),{pass,total}});\n        }\n\n        while(extraStudents--){\n            auto [average,data] = pq.top();\n            pq.pop();\n            int pass = data.first;\n            int total = data.second;\n            sum -= (double)pass/total;\n            pass++;\n            total++;\n            sum += (double)pass/total;\n            pq.push({calcAverage(pass,total),{pass,total}});\n        }\n        return sum / classes.size();\n    }\n};\n```\n\n---\n\n![upvoting_cat.jpeg](https://assets.leetcode.com/users/images/eb3d5228-d6f5-4b75-a7a1-557988245f91_1734479149.4344368.jpeg)\n
['Array', 'Math', 'Binary Search', 'Greedy', 'Heap (Priority Queue)', 'C++']