PriorityQueue | Solution for LeetCode#1792
IntuitionThe problem requires maximizing the average pass ratio across all classes by optimally allocating extra students. The key insight is that we should pri
![image.png](https://assets.leetcode.com/users/images/ef4820a8-9e41-41bf-80be-c679b214a5d6_1734246880.0748646.png)\n\n# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem requires maximizing the average pass ratio across all classes by optimally allocating extra students. The key insight is that we should prioritize adding students to classes where the increase in pass ratio is the highest.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Use a max heap (priority queue) to store the potential increase in pass ratio for each class if we add one student.\n2. Initialize the sum of current pass ratios.\n3. For each extra student:\n\t- Remove the class with the highest potential increase from the heap.\n\t- Update the sum of pass ratios with this increase.\n\t- Update the class\'s pass/total counts.\n\t- Recalculate the new potential increase and add it back to the heap.\n4. Return the final average pass ratio.\n\n# Complexity\n- Time complexity: O((n + m) log n), where n is the number of classes and m is the number of extra students. We perform m heap operations, each taking O(log n) time.\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:  O(n) for the priority queue.\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```java []\nclass Solution {\n    public double maxAverageRatio(int[][] classes, int extraStudents) {        \n        int n=classes.length;\n        PriorityQueue<double[]> pq=new PriorityQueue<>((a,b)->Double.compare(b[0], a[0]));\n\n\n        double sumVal=0;      \n\n        for(int i=0; i<n;  i++){\n            double val1=(double)classes[i][0]/classes[i][1];\n            double val2=(double)(classes[i][0]+1)/(classes[i][1]+1);\n            double val=val2-val1;\n            pq.add(new double[]{val, i});\n            sumVal +=val1;\n        }\n\n       \n\n        for(int j=0; j<extraStudents; j++){\n            double[] que=pq.poll();\n            double val=que[0];\n            int i=(int)que[1];\n            \n            sumVal +=val;\n            classes[i][0]+=1;\n            classes[i][1]+=1;\n\n            double val1=(double)classes[i][0]/classes[i][1];\n            double val2=(double)(classes[i][0]+1)/(classes[i][1]+1);\n            val=val2-val1;\n            pq.add(new double[]{val, i});\n\n        }\n\n        return sumVal/n;\n    }\n}\n```
['Heap (Priority Queue)', 'Java']