Most Optimal Heap(Priority Queue) O(k + m logk) Approach 👀
IntuitionTo maximize the average pass ratio, we should allocate extra students to classes where the gain (improvement in pass ratio) is largest. By focusing on
# Intuition\nTo maximize the average pass ratio, we should allocate extra students to classes where the gain (improvement in pass ratio) is largest. By focusing on the classes that benefit the most from an extra student, we maximize the overall pass ratio.\n\n# Approach\n1. **Gain Function:** Calculate the gain for adding one student to a class:\n```\n gain = (p + 1) / (t + 1) - (p) / (t)\n```\nwhere `p` is the number of passed students and `t` is the total number of students.\n\n2. **Max-Heap:** Use a max-heap (priority queue) to prioritize classes by their gain. Store negative gains to make the heap behave like a max-heap.\n\n3. **Allocate Extra Students:** For each extra student, pop the class with the highest gain, update its values, and push it back into the heap.\n\n4. **Final Average:** After distributing all extra students, compute the final average pass ratio by averaging the pass ratios of all classes.\n# Complexity\n**Time complexity:**\n- Heap operations (`push` and `pop`) take $$O(log k)$$, where `k` is the number of classes.\n- Distributing $$m$$ extra students involves $$m$$ heap operations.\n- Overall complexity: $$O(k + mlogk)$$.\n\n**Space complexity:**  \n- The heap requires $$O(k)$$ space.\n\n\n# Code\n```python3 []\nclass Solution:\n    def maxAverageRatio(self, cls: List[List[int]], extra: int) -> float:\n        cls = [(p/t - (p+1)/(t+1), p, t) for p, t in cls]\n        heapify(cls)\n\n        if cls[0][0] == 0:\n            return 1\n\n        for _ in range(extra):\n            _, p, t = heappop(cls)\n            heappush(cls, ((p+1)/(t+1) - (p+2)/(t+2), p+1, t+1))\n\n        return sum(p/t for _, p, t in cls) / len(cls)\n\n```\n```C++ []\nclass Solution {\npublic:\n    double maxAverageRatio(vector<vector<int>>& cls, int extra) {\n        // Lambda function to calculate the gain of adding one student\n        auto gain = [](int p, int t) {\n            return (double)(p + 1) / (t + 1) - (double)p / t;\n        };\n\n        // Max-heap to store the classes by the gain in descending order\n        priority_queue<pair<double, pair<int, int>>> pq;\n\n        // Push all classes into the heap, prioritize by the gain\n        for (auto& c : cls) {\n            pq.push({gain(c[0], c[1]), {c[0], c[1]}});\n        }\n\n        // Distribute the extra students\n        while (extra--) {\n            auto [g, pt] = pq.top();\n            pq.pop();\n            int p = pt.first, t = pt.second;\n            pq.push({gain(p + 1, t + 1), {p + 1, t + 1}});\n        }\n\n        // Compute the final average pass ratio\n        double sum = 0;\n        while (!pq.empty()) {\n            auto [g, pt] = pq.top();\n            pq.pop();\n            sum += (double)pt.first / pt.second;\n        }\n\n        return sum / cls.size();\n    }\n};\n```\n```Java []\nclass Solution {\n    public double maxAverageRatio(int[][] cls, int extra) {\n        // Gain calculation\n        PriorityQueue<double[]> pq = new PriorityQueue<>((a, b) -> Double.compare(b[0], a[0]));\n\n        for (int[] c : cls) {\n            int p = c[0], t = c[1];\n            pq.offer(new double[]{gain(p, t), p, t});\n        }\n\n        // Distribute extra students\n        while (extra-- > 0) {\n            double[] top = pq.poll();\n            double g = top[0];\n            int p = (int) top[1], t = (int) top[2];\n            pq.offer(new double[]{gain(p + 1, t + 1), p + 1, t + 1});\n        }\n\n        // Compute the final average pass ratio\n        double sum = 0;\n        for (double[] c : pq) {\n            sum += c[1] / c[2];\n        }\n\n        return sum / cls.length;\n    }\n\n    // Helper to calculate gain\n    private double gain(int p, int t) {\n        return (double) (p + 1) / (t + 1) - (double) p / t;\n    }\n}\n\n```\n![c7a0bae9-3d2d-4f75-a1cb-b5eb09aba264_1733973284.784742.png](https://assets.leetcode.com/users/images/44a8108a-c7fc-4343-913d-a47fd049a61f_1734229281.6514635.png)\n\n
['Heap (Priority Queue)', 'C++', 'Java', 'Python3']