JAVA || Easiest Code || Simple Approach || Beginner Friendly 🔥🚀
IntuitionThe goal is to maximize the average pass ratio after assigning extraStudents to the classes. The pass ratio for each class is defined as the number of
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\nThe goal is to maximize the average pass ratio after assigning `extraStudents` to the classes. The pass ratio for each class is defined as the number of passing students divided by the total number of students in that class. By assigning extra students to classes that will benefit the most (i.e., where the improvement in pass ratio is the largest), we maximize the average pass ratio. This requires calculating the improvement in pass ratio after adding one student and distributing the `extraStudents` accordingly.\n\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. **Initial Setup**:\n   - We initialize a priority queue (`pq`) that stores classes, prioritized by the potential improvement in pass ratio after adding an extra student.\n   - Each class is represented by an array of three values: the improvement after adding one student, the current number of passing students (`pass`), and the total number of students (`total`).\n   \n2. **Priority Queue Operations**:\n   - For each class, we compute the improvement if one student is added (i.e., the difference between the pass ratio after adding one student and the current pass ratio).\n   - We then push this information into the priority queue, where the class with the maximum improvement is given higher priority.\n   \n3. **Distributing Extra Students**:\n   - While there are still extra students to assign, we repeatedly:\n     - Pop the class with the maximum potential improvement from the queue.\n     - Assign one student to this class.\n     - Recompute the improvement (since adding a student affects the pass ratio) and push the updated class back into the queue.\n   \n4. **Final Calculation**:\n   - After all extra students are assigned, we compute the total pass ratio for all classes by summing their pass ratios and then dividing by the number of classes to get the average.\n\n# Complexity\n- Time complexity: - **O(n log n)**:\n  - The priority queue operations (`offer` and `poll`) take `O(log n)` time, where `n` is the number of classes.\n  - We perform a constant number of operations (each involving a `poll`, an update, and a `offer`) for each extra student, so the complexity due to extra students is `O(extraStudents log n)`.\n  - The final loop that calculates the total pass ratio also takes `O(n)` time.\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: - **O(n)**:\n  - We store the class information (pass, total, and improvement) in the priority queue. The maximum number of elements in the queue at any time is equal to the number of classes, so the space complexity is `O(n)`.\n  - No other significant data structures are used that would contribute to additional space usage.\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```java []\n\nclass Solution {\n    public double maxAverageRatio(int[][] classes, int extraStudents) {\n        // Priority queue to store classes by their potential improvement in pass ratio\n        PriorityQueue<double[]> pq = new PriorityQueue<>((a, b) -> Double.compare(b[0], a[0]));\n\n        // Calculate the initial improvement and add classes to the queue\n        for (int[] c : classes) {\n            int pass = c[0], total = c[1];\n            double improvement = ((double)(pass + 1) / (total + 1)) - ((double) pass / total);\n            pq.offer(new double[]{improvement, pass, total});\n        }\n\n        // Distribute extra students\n        while (extraStudents > 0) {\n            // Extract the class with the largest improvement\n            double[] top = pq.poll();\n            double improvement = top[0];\n            int pass = (int) top[1];\n            int total = (int) top[2];\n\n            // Assign one extra student\n            pass++;\n            total++;\n\n            // Recalculate the improvement and push back to the queue\n            double newImprovement = ((double)(pass + 1) / (total + 1)) - ((double) pass / total);\n            pq.offer(new double[]{newImprovement, pass, total});\n            extraStudents--;\n        }\n\n        // Calculate the final average pass ratio\n        double totalRatio = 0;\n        while (!pq.isEmpty()) {\n            double[] top = pq.poll();\n            int pass = (int) top[1];\n            int total = (int) top[2];\n            totalRatio += (double) pass / total;\n        }\n\n        return totalRatio / classes.length;\n    }\n}\n```
['Array', 'Greedy', 'Heap (Priority Queue)', 'Java']