Priority queue O((m+n)log n) Solution 100% Beats 
🧠 Intuition 🤔The problem is about maximizing the overall average ratio by distributing extra students across the classes. The key idea is to identify which clas
# \uD83E\uDDE0 Intuition \uD83E\uDD14  \nThe problem is about maximizing the overall average ratio by distributing extra students across the classes. The key idea is to identify which class benefits the most from each extra student. This can be achieved by calculating the improvement, or "gain," for adding a student to each class and prioritizing those with the highest gain.\n\n---\n\n# \uD83D\uDEE0\uFE0F Approach \uD83D\uDCDA  \n\n1. **Gain Calculation**:  \n   - Calculate the improvement in ratio by adding one extra student to a class.  \n   - The gain is the difference between the new ratio and the current ratio of a class.  \n\n2. **Prioritize with a Max-Heap**:  \n   - Use a max-heap to track which class yields the highest gain from an extra student.  \n   - Each entry in the heap contains the current gain and the class\'s pass and total values.  \n\n3. **Distribute Extra Students**:  \n   - Remove the class with the highest gain from the heap.  \n   - Update the pass and total counts for that class by adding one student.  \n   - Recalculate its gain and reinsert it into the heap.  \n   - Repeat this process for all extra students.\n\n4. **Calculate Final Average**:  \n   - Sum the updated ratios of all classes and divide by the total number of classes to get the final average.  \n\n---\n\n# \u23F1\uFE0F Complexity Analysis \uD83D\uDE80  \n\n- **Time Complexity**:  \n  - Building the max-heap takes O(n log n).  \n  - Each student distribution involves extracting the max and reinserting into the heap, which takes O(log n).  \n  - For `extraStudents`, the total complexity is O(extraStudents * log n).  \n\n- **Space Complexity**:  \n  - The space complexity is O(n) for the heap.  \n\n---\n\n# Code\n```C# []\nusing System;\nusing System.Collections.Generic;\n\npublic class Solution {\n    public double MaxAverageRatio(int[][] classes, int extraStudents) {\n        PriorityQueue<(double gain, int pass, int total), double> maxHeap = new PriorityQueue<(double, int, int), double>(Comparer<double>.Create((a, b) => b.CompareTo(a)));\n        double sum = 0.0;\n\n        foreach (var cls in classes) {\n            int pass = cls[0], total = cls[1];\n            sum += (double)pass / total;\n            maxHeap.Enqueue((Gain(pass, total), pass, total), Gain(pass, total));\n        }\n\n        for (int i = 0; i < extraStudents; i++) {\n            var top = maxHeap.Dequeue();\n            int pass = top.pass, total = top.total;\n            sum -= (double)pass / total;\n            pass++;\n            total++;\n            sum += (double)pass / total;\n            maxHeap.Enqueue((Gain(pass, total), pass, total), Gain(pass, total));\n        }\n\n        return sum / classes.Length;\n    }\n\n    private double Gain(int pass, int total) {\n        return (double)(pass + 1) / (total + 1) - (double)pass / total;\n    }\n}\n```\n```Python3 []\nclass Solution:\n    def maxAverageRatio(self, classes: List[List[int]], extraStudents: int) -> float:\n        import heapq\n\n        def gain(pass_, total):\n            return (pass_ + 1) / (total + 1) - pass_ / total\n\n        max_heap = []\n        sum_ = 0.0\n\n        for pass_, total in classes:\n            sum_ += pass_ / total\n            heapq.heappush(max_heap, (-gain(pass_, total), pass_, total))\n\n        for _ in range(extraStudents):\n            current_gain, pass_, total = heapq.heappop(max_heap)\n            sum_ -= pass_ / total\n            pass_ += 1\n            total += 1\n            sum_ += pass_ / total\n            heapq.heappush(max_heap, (-gain(pass_, total), pass_, total))\n\n        return sum_ / len(classes)\n\n```\n```Java []\nclass Solution {\n    public double maxAverageRatio(int[][] classes, int extraStudents) {\n        // Lambda-like comparator for calculating gain in Java\n        PriorityQueue<double[]> maxHeap = new PriorityQueue<>((a, b) -> Double.compare(b[0], a[0]));\n        double sum = 0.0;\n\n        // Initialize the heap with gains and add the initial ratios to sum\n        for (int[] cls : classes) {\n            int pass = cls[0], total = cls[1];\n            double currentRatio = (double) pass / total;\n            double gain = ((double) (pass + 1) / (total + 1)) - currentRatio;\n            sum += currentRatio;\n            maxHeap.offer(new double[]{gain, pass, total});\n        }\n\n        // Distribute extra students to maximize the average ratio\n        for (int i = 0; i < extraStudents; i++) {\n            double[] top = maxHeap.poll();\n            double gain = top[0];\n            int pass = (int) top[1];\n            int total = (int) top[2];\n\n            // Update the sum by removing the old ratio and adding the new one\n            sum -= (double) pass / total;\n            pass++;\n            total++;\n            sum += (double) pass / total;\n\n            // Recalculate the gain and push back into the heap\n            double newGain = ((double) (pass + 1) / (total + 1)) - ((double) pass / total);\n            maxHeap.offer(new double[]{newGain, pass, total});\n        }\n\n        // Return the final average\n        return sum / classes.length;\n    }\n}\n\n```\n```cpp []\nclass Solution {\npublic:\n    double maxAverageRatio(vector<vector<int>>& classes, int extraStudents) {\n        auto gain = [](double pass, double total) {\n            return (pass + 1) / (total + 1) - pass / total;\n        };\n\n        priority_queue<pair<double, pair<int, int>>> maxHeap;\n\n        double sum = 0.0;\n\n        for (const auto& cls : classes) {\n            int pass = cls[0], total = cls[1];\n            sum += (double)pass / total;  \n            maxHeap.push({gain(pass, total), {pass, total}});\n        }\n\n        for (int i = 0; i < extraStudents; ++i) {\n            auto [currentGain, data] = maxHeap.top(); maxHeap.pop();\n            int pass = data.first, total = data.second;\n\n            sum -= (double)pass / total;\n            pass += 1;\n            total += 1;\n            sum += (double)pass / total;\n\n            maxHeap.push({gain(pass, total), {pass, total}});\n        }\n\n        return sum / classes.size();\n    }\n};\n\n```
['Array', 'Heap (Priority Queue)', 'C++', 'Java', 'Python3', 'C#']