Question is poorly asked | Key point here is marginal gain | Easy to read
IntuitionApproachComplexity

Time complexity:

O(n * log(n))
logn (Enqueqe an element to pq)



Space complexity:

O(n)


Code
# Intuition\n    - the key here is, we want to maximize the avg.\n    - what are the candiates which will give max avg, this will be calculated by marginal gain\n    - Marginal Gain = (pass + 1) / (total + 1) - pass / total;\n# Approach\n    - we will iterate through each class, find the candiated which will give max marginal gain.\n    - Remember we are not incrementing pass or total here while adding to PQ\n    - Now process extra student, at this point we will increase pass & total count\n\n# Complexity\n- Time complexity:\n    - O(n * log(n))\n    - logn (Enqueqe an element to pq)\n\n- Space complexity:\n    - O(n)\n# Code\n```csharp []\npublic class Solution \n{\n    public double MaxAverageRatio(int[][] classes, int extraStudents) \n    {\n     /*\n        the problem is poorly described\n            we ahve to add a student to class in suuch a way that marginal gain increases\n            marginal gain = newGain - oldGain\n            newGain = pass + 1 / total + 1 - pass / total\n            so focus on the classes which is giving more gain not on the classes with least gain\n     */   \n\n        var pq = new PriorityQueue<(int pass, int total), double>();\n        foreach (var c in classes) \n        {\n            int pass = c[0];\n            int total = c[1];\n            pq.Enqueue((pass, total), -Gain(pass, total));\n        }\n\n        while (extraStudents-- > 0) \n        {\n            (int pass, int total) = pq.Dequeue();\n            ++pass; //1 student added here\n            ++total; // 1 student added to overall class\n            pq.Enqueue((pass, total), -Gain(pass, total));\n        }\n\n        double avg = 0;\n        while (pq.Count > 0) \n        {\n            (int pass, int total) = pq.Dequeue();\n            avg += (double)pass/total;\n        }\n\n        return (double)avg / classes.Length;\n    }\n\n    double Gain(int pass, int total) => (double) (pass + 1) / (total + 1) - (double) pass / total;\n}\n```
['Greedy', 'Heap (Priority Queue)', 'C#']