Java Solution for Maximum Average Pass Ratio Problem
IntuitionThe problem requires maximizing the average pass ratio across multiple classes by distributing a limited number of extra students. The key observation
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem requires maximizing the average pass ratio across multiple classes by distributing a limited number of extra students. The key observation is that the increase in pass ratio diminishes as more students are added to a class. Therefore, we should prioritize assigning students to the class where the addition results in the largest increase in pass ratio.\n\nTo achieve this, a greedy approach is used, where a priority queue (max heap) is leveraged to repeatedly pick the class that benefits the most from an extra student.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1.\tInitial Calculation:\n\t\u2022\tFor each class, calculate the potential improvement in pass ratio by adding one student.\n\t\u2022\tStore these improvements in a max heap along with the current number of passing and total students.\n2.\tDistribute Extra Students:\n\t\u2022\tWhile there are extra students to assign:\n\t\u2022\tExtract the class with the highest improvement from the heap.\n\t\u2022\tAdd an extra student to this class (i.e., increment passi and totali).\n\t\u2022\tRecalculate the new improvement and push the updated class back into the heap.\n3.\tCompute Final Average:\n\t\u2022\tOnce all extra students are assigned, calculate the average pass ratio by summing up the pass ratios of all classes and dividing by the number of classes.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n1.\tBuilding the Heap:\n\t\u2022\tFor n classes, inserting them into the heap takes O(n . log n).\n2.\tAssigning Extra Students:\n\t\u2022\tFor each of the extraStudents, we:\n\t\u2022\tExtract the maximum improvement from the heap (O(log n)).\n\t\u2022\tRecalculate the improvement and push it back into the heap (O(log n)).\n\t\u2022\tThis step takes O(extraStudents . log n).\n3.\tFinal Computation:\n\t\u2022\tIterating over the heap to compute the final pass ratio takes O(n).\n\nTotal Time Complexity: O((n + extraStudents) . log n)\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n1.\tHeap Storage:\n\t\u2022\tThe heap stores up to n classes, where each entry includes the improvement, passing students, and total students.\n\t\u2022\tSpace required: O(n).\n2.\tAuxiliary Space:\n\t\u2022\tA few variables are used to store intermediate results, so additional space usage is negligible.\n\nTotal Space Complexity: O(n)\n\n# Code\n```java []\nclass Solution {\n    public double maxAverageRatio(int[][] classes, int extraStudents) {\n        PriorityQueue<double[]> maxHeap = new PriorityQueue<>((a, b) -> Double.compare(b[0], a[0]));\n        for (int[] clazz : classes) {\n            int passi = clazz[0];\n            int totali = clazz[1];\n            double improvement = improvement(passi, totali);\n            maxHeap.offer(new double[]{improvement, passi, totali});\n        }\n        \n        while (extraStudents > 0) {\n            double[] top = maxHeap.poll();\n            int passi = (int) top[1];\n            int totali = (int) top[2];\n            \n            passi++;\n            totali++;\n            extraStudents--;\n            \n            double newImprovement = improvement(passi, totali);\n            maxHeap.offer(new double[]{newImprovement, passi, totali});\n        }\n        double totalRatio = 0.0;\n        while (!maxHeap.isEmpty()) {\n            double[] clazz = maxHeap.poll();\n            int passi = (int) clazz[1];\n            int totali = (int) clazz[2];\n            totalRatio += (double) passi / totali;\n        }\n        \n        return totalRatio / classes.length;\n    }\n    private double improvement(int passi, int totali) {\n        return ((double) (passi + 1) / (totali + 1)) - ((double) passi / totali);\n    }\n}\n```
['Java']