Java O(mlogc) solution with clear explanation and comments
The challenge that I faced was to know where to add the extra student. We cannot simply add a student to a class with lowest pass ratio.\n\nWhy? For eg:  consid
The challenge that I faced was to know where to add the extra student. We cannot simply add a student to a class with lowest pass ratio.\n\nWhy? For eg:  consider the ratios  2/3 (0.6666) and 3/5 (0.6) \nif we add 1 student to  2/3 -> 3/4 (0.75)\nor\nif we add 1 student to 3/5 -> 4/6 (0.6666)\n\nFrom above we see that we cannot just simply add the student to lowest ratio (3/5).\n\nSo the idea is to compute the ratio increases (if we add one student) for each class and store in maxHeap.\nThe top of the heap will always have the class which is the best candidate to add the new student.\n\n**Code:**\n```\nclass Solution {\n\n    // T = O(mlogc)  S=O(c)   c=no. of classes   m= extra students\n    public double maxAverageRatio(int[][] classes, int extraStudents) {\n        \n        double totalPassRatios = 0.0;\n        // track the max new Pass Ratio (if a student is added to a class)\n        // format: double[] {passRatio increase if a student is added,   pass count,   student count}\n        PriorityQueue<double[]> maxHeap = new PriorityQueue<>((a,b) -> Double.compare(b[0], a[0]));\n        \n        for(int i=0; i< classes.length; i++) {\n            // pass ratio\n            double passRatio = (double) classes[i][0]/classes[i][1];\n            // alternate pass ratio if a student is added\n            double altPassRatio = (double) (classes[i][0]+1)/(classes[i][1]+1);\n            \n            maxHeap.add(new double[]{altPassRatio-passRatio, classes[i][0], classes[i][1]});\n        }\n        \n        while(!maxHeap.isEmpty() && extraStudents > 0) {\n            double[] top = maxHeap.poll();\n            double passRatio = (double) (top[1]+1)/(top[2]+1);\n            double altPassRatio = (double) (top[1]+2)/(top[2]+2);\n            // update the maxHeap\n            maxHeap.add(new double[]{altPassRatio-passRatio, top[1]+1, top[2]+1});\n            \n            extraStudents--; // decrement the extraStudents\n        }\n        \n        // add all the ratios from Heap\n        while(!maxHeap.isEmpty()) {            \n            double[] top = maxHeap.poll();\n            double passRatio = (double) (top[1])/(top[2]);\n            totalPassRatios += passRatio;\n        }\n        \n        return totalPassRatios / classes.length;\n    }\n}\n```
[]