[Java] Greedy solution using priority queue (with trick for early termination)
Use a max heap: the comparator compares the passing ratio with adding one more student.\nFor a class, if number of passing sutdents is equal to total number of 
Use a max heap: the comparator compares the passing ratio with adding one more student.\nFor a class, if number of passing sutdents is equal to total number of students, it\'s passing ratio is already 1 and adding more passing students doesn\'t help further.\nThus, only add those with potential to increase the passing ratio to the priority queue. \n If priority queue is empty, we can terminate early, because we know adding more passing students won\'t help further.   \n\n```\nclass Solution {\n    public double maxAverageRatio(int[][] classes, int extraStudents) {\n        int n = classes.length;\n        PriorityQueue<int[]> pq = new PriorityQueue<>((a,b)->Double.compare(ratioIncr(b),ratioIncr(a)));   // max pq\n        double currRating = 0.0;\n        for (int[] rating : classes) {\n            currRating += (double)rating[0] / rating[1];\n            if (rating[0] != rating[1]) {  // only add those with potential to increase the passing ratio\n                pq.offer(rating);\n            }\n        }\n        currRating /= n;\n        if (pq.isEmpty())  // early termination\n            return currRating;\n        while (extraStudents-- > 0) {\n            int[] item = pq.poll();\n            currRating += ratioIncr(item)/n;\n            item[0]++; item[1]++;\n            pq.offer(item);\n        }\n        return currRating;\n    }\n\n    private double ratioIncr(int[] item) {\n        double ratio1 = (double)item[0] / item[1];\n        double ratio2 = (double)(item[0]+1) / (item[1]+1);\n        return ratio2 - ratio1;\n    }\n}\n```
[]