✅ Easy to Understand | Greedy | Priority Queue | Detailed Video Explanation🔥
IntuitionTo maximize the average pass ratio across all classes, we need to distribute the extra students strategically. Intuitively, adding a student to a class
# Intuition\nTo maximize the average pass ratio across all classes, we need to distribute the extra students strategically. Intuitively, adding a student to a class where it has the maximum impact on the pass ratio is the optimal approach. By focusing on the marginal gain in pass ratio for each class, we can prioritize classes that yield the most significant improvement.\n\n# Approach\n1. **Understand the Gain in Pass Ratio**: For each class, calculate the current pass ratio and the new pass ratio if one student is added. The difference between the new and current pass ratios represents the gain.\n\n2. **Use a Priority Queue**: Employ a max-heap (priority queue) to keep track of classes based on their potential gain in pass ratio. The class with the highest gain is at the top.\n\n3. **Distribute Extra Students**: Repeatedly add an extra student to the class with the highest gain (the top of the priority queue). Update the class\'s pass ratio and reinsert it into the queue after adjusting its parameters.\n\n4. **Calculate the Final Average**: After all extra students have been distributed, calculate the average pass ratio by summing up the pass ratios of all classes and dividing by the total number of classes.\n\n# Complexity\n- **Time complexity**:\n  - Initializing the priority queue: $$O(n \\log n)$$ (for inserting all classes).\n  - Processing extra students: $$O(k \\log n)$$ (where \\(k\\) is the number of extra students, and \\(n\\) is the number of classes).\n  - Overall: $$O((n + k) \\log n)$$.\n\n- **Space complexity**:\n  - The priority queue stores all classes: $$O(n)$$.\n\n\n\n# Code\n```java []\nclass Solution {\n\n    // Comparator method to compare the gain in pass ratio when an extra student is added\n    private static int compare(int[] c1, int[] c2){\n        // Current pass ratios\n        double pr1 = c1[0] * 1.0 / c1[1];\n        double pr2 = c2[0] * 1.0 / c2[1];\n\n        // New pass ratios if one student is added\n        double npr1 = (c1[0] + 1.0) / (c1[1] + 1.0);\n        double npr2 = (c2[0] + 1.0) / (c2[1] + 1.0);\n\n        // Gain in pass ratios\n        double d1 = npr1 - pr1;\n        double d2 = npr2 - pr2;\n\n        // Compare based on the higher gain in pass ratio\n        return Double.compare(d2, d1);\n    }\n\n    // Helper method to calculate the pass ratio of a class\n    private double passRatio(int[] c){\n        return c[0] * 1.0 / c[1];\n    }\n\n    // Method to maximize the average pass ratio after distributing extra students\n    public double maxAverageRatio(int[][] classes, int extraStudents) {\n        int n = classes.length;\n\n        // Priority queue to store classes, ordered by the comparator\n        PriorityQueue<int[]> pq = new PriorityQueue<>(Solution::compare);\n\n        double totalPR = 0.0; // To keep track of the total pass ratio\n\n        // Add all classes to the priority queue and calculate the initial total pass ratio\n        for(int i = 0; i < n; i++){\n            int[] curr = classes[i];\n            pq.offer(new int[]{curr[0], curr[1]});\n            totalPR += passRatio(curr);\n        }\n\n        // Distribute the extra students\n        while(extraStudents > 0){\n            // Poll the class that has the highest gain in pass ratio when an extra student is added\n            int[] bestClass = pq.poll();\n\n            // Update the total pass ratio by removing the old ratio and adding the new one\n            totalPR -= passRatio(bestClass);\n            bestClass[0]++; // Increment the number of passes\n            bestClass[1]++; // Increment the total number of students\n            totalPR += passRatio(bestClass);\n\n            // Re-add the updated class back to the priority queue\n            pq.offer(bestClass);\n            extraStudents--; // Decrease the count of extra students\n        }\n\n        // Return the average pass ratio after distributing all extra students\n        return totalPR / n;\n    }\n}\n\n```\n```c++ []\n#include <vector>\n#include <queue>\n#include <functional>\n\nusing namespace std;\n\nclass Solution {\npublic:\n    // Comparator function to compare the gain in pass ratio\n    static bool compare(const vector<int>& c1, const vector<int>& c2) {\n        double pr1 = c1[0] * 1.0 / c1[1];\n        double pr2 = c2[0] * 1.0 / c2[1];\n\n        double npr1 = (c1[0] + 1.0) / (c1[1] + 1.0);\n        double npr2 = (c2[0] + 1.0) / (c2[1] + 1.0);\n\n        double d1 = npr1 - pr1;\n        double d2 = npr2 - pr2;\n\n        return d1 < d2; // Max-heap based on gain in pass ratio\n    }\n\n    double passRatio(const vector<int>& c) {\n        return c[0] * 1.0 / c[1];\n    }\n\n    double maxAverageRatio(vector<vector<int>>& classes, int extraStudents) {\n        priority_queue<vector<int>, vector<vector<int>>, function<bool(const vector<int>&, const vector<int>&)>> pq(compare);\n\n        double totalPR = 0.0;\n\n        for (const auto& c : classes) {\n            pq.push(c);\n            totalPR += passRatio(c);\n        }\n\n        while (extraStudents > 0) {\n            auto bestClass = pq.top();\n            pq.pop();\n\n            totalPR -= passRatio(bestClass);\n            bestClass[0]++;\n            bestClass[1]++;\n            totalPR += passRatio(bestClass);\n\n            pq.push(bestClass);\n            extraStudents--;\n        }\n\n        return totalPR / classes.size();\n    }\n};\n\n```\n```python []\nimport heapq\n\nclass Solution:\n    def passRatio(self, c):\n        return c[0] / c[1]\n\n    def maxAverageRatio(self, classes, extraStudents):\n        # Comparator function to calculate gain in pass ratio\n        def compare(c):\n            pr = c[0] / c[1]\n            npr = (c[0] + 1) / (c[1] + 1)\n            return pr - npr\n\n        # Use a max-heap, so invert the comparator value for heapq\n        pq = []\n        for c in classes:\n            heapq.heappush(pq, (-compare(c), c))\n\n        totalPR = sum(self.passRatio(c) for c in classes)\n\n        while extraStudents > 0:\n            _, bestClass = heapq.heappop(pq)\n            totalPR -= self.passRatio(bestClass)\n            bestClass[0] += 1\n            bestClass[1] += 1\n            totalPR += self.passRatio(bestClass)\n            heapq.heappush(pq, (-compare(bestClass), bestClass))\n            extraStudents -= 1\n\n        return totalPR / len(classes)\n\n```\n\n\nLeetCode 1792 Maximum Average Pass Ratio | Greedy | Heap | Asked in Amazon\nhttps://youtu.be/rQZSm61A4N4\n\n\n\n\n\n\n\n\n\n\n\n\n
['Array', 'Greedy', 'Heap (Priority Queue)', 'Python', 'C++', 'Java']