C# - Fast - 962ms - PriorityQueue of improvement of pass ratio
Intuition / ApproachThe thing to figure out is which one class would be made better by the most by adding a brilliant student. That would be the one that would
![image.png](https://assets.leetcode.com/users/images/03f0de69-2c4a-4f1d-82b5-ab796da73812_1734226950.333941.png)\n\n# Intuition / Approach\nThe thing to figure out is which one class would be made better by the most by adding a brilliant student. That would be the one that would make the biggest impact on the pass ratio for her class. So we calculate this with (pass+1)/(total+1) - pass/total. Our first instinct might be to sort by this, but then for every extraStudent, we would have to resort the list. In cases like that, the answer is to use a heap. We just add all the classes to the min heap using the negative of our biggest impact calculation, then for each extra student, get the lowest value item, adjust it by adding the brilliant student and put it back on the queue. Then we finally calculate the average.\n\nAs a minor optimization, we use .Peek and .DequeueEnqueue which are an O(1) and an O(log n) operation respectively, rather than a .Dequeue and .Enqueue which would each be an O(log n) operation.\n\nAs another optimization, we use .UnorderedItems to access the current items in the heap rather than using .Dequeue to get each item, making the final averaging operation O(n) rather than O(n log n).\n\n# Complexity\n- Time complexity: $$O(n log n + m log n)$$ where n is the number of classes and m is the number of extra students\n- Space complexity: $$O(n)$$\n\n# Code\n```csharp []\npublic class Solution {\n    public double MaxAverageRatio(int[][] classes, int extraStudents) {\n        PriorityQueue<(int p,int t),double> pq=new(classes.Select(c=>((c[0],c[1]), 1d*c[0]/c[1]-(c[0]+1d)/(c[1]+1))));\n        while(extraStudents-- > 0) {\n            var cl=pq.Peek();\n            pq.DequeueEnqueue((cl.p+1,cl.t+1), (cl.p+1d)/(cl.t+1)-(cl.p+2d)/(cl.t+2));\n        }\n        return pq.UnorderedItems.Average(c=>1d*c.Item1.p/c.Item1.t);\n    }\n}\n```
['Array', 'Greedy', 'Heap (Priority Queue)', 'C#']