There is a school that has classes of students and each class will be having a final exam. You are given a 2D integer array classes, where classes[i] = [passi, totali]. You know beforehand that in the ith class, there are totali total students, but only passi number of students will pass the exam.

You are also given an integer extraStudents. There are another extraStudents brilliant students that are guaranteed to pass the exam of any class they are assigned to. You want to assign each of the extraStudents students to a class in a way that maximizes the average pass ratio across all the classes.

The pass ratio of a class is equal to the number of students of the class that will pass the exam divided by the total number of students of the class. The average pass ratio is the sum of pass ratios of all the classes divided by the number of the classes.

Return the maximum possible average pass ratio after assigning the extraStudents students. Answers within 10-5 of the actual answer will be accepted.

&nbsp;
Example 1:

Input: classes = [[1,2],[3,5],[2,2]], extraStudents = 2
Output: 0.78333
Explanation: You can assign the two extra students to the first class. The average pass ratio will be equal to (3/4 + 3/5 + 2/2) / 3 = 0.78333.


Example 2:

Input: classes = [[2,4],[3,9],[4,5],[2,10]], extraStudents = 4
Output: 0.53485


&nbsp;
Constraints:


	1 &lt;= classes.length &lt;= 105
	classes[i].length == 2
	1 &lt;= passi &lt;= totali &lt;= 105
	1 &lt;= extraStudents &lt;= 105


class Solution:
	def maxAverageRatio(self, classes: List[List[int]], extraStudents: int) -> float:
		
		n = len(classes)
		
		impacts = [0]*n
		minRatioIndex = 0
		
		# calculate and store impacts for each class in form of tuples -> (-impactValue, passCount, totalCount)
		for i in range(n):
			passCount = classes[i][0]
			totalCount = classes[i][1]
			
			# calculate the impact  for class i
			currentRatio = passCount/totalCount
			expectedRatioAfterUpdate = (passCount+1)/(totalCount+1)
			impact = expectedRatioAfterUpdate - currentRatio
			
			impacts[i] = (-impact, passCount, totalCount)  # note the - sign for impact
			
		heapq.heapify(impacts)
		
		while(extraStudents > 0):
			# pick the next class with greatest impact 
			_, passCount, totalCount = heapq.heappop(impacts)
			
			# assign a student to the class
			passCount+=1
			totalCount+=1
			
			# calculate the updated impact  for current class
			currentRatio = passCount/totalCount
			expectedRatioAfterUpdate = (passCount+1)/(totalCount+1)
			impact = expectedRatioAfterUpdate - currentRatio
			
			# insert updated impact back into the heap
			heapq.heappush(impacts, (-impact, passCount, totalCount))
			extraStudents -= 1
		
		result = 0
			
		# for all the updated classes calculate the total passRatio 
		for _, passCount, totalCount in impacts:
			result += passCount/totalCount
			
		# return the average pass ratio
		return result/n
class Solution {
    public double maxAverageRatio(int[][] classes, int extraStudents) {
        PriorityQueue<double[]> pq = new PriorityQueue<>(new Comparator<double[]>(){
            public int compare(double[] a, double[] b){
                double adiff = (a[0]+1)/(a[1]+1) - (a[0]/a[1]);
                double bdiff = (b[0]+1)/(b[1]+1) - (b[0]/b[1]);
                if(adiff==bdiff) return 0;
                return adiff>bdiff? -1:1;
            }
        });

        for(int[] c:classes) pq.add(new double[]{c[0],c[1]});

        for(int i =0;i<extraStudents;i++){
            double[] curr = pq.poll();
            pq.add(new double[]{curr[0]+1,curr[1]+1});
        }

        double sum = 0;
        while(!pq.isEmpty()){
            double[] curr = pq.poll();
            sum+=curr[0]/curr[1];
        }

        return sum/classes.length;
    }
}
struct cmp{
    bool operator()(pair<int,int> a, pair<int,int> b){
        double ad = (a.first+1)/(double)(a.second+1) - (a.first)/(double)a.second;
        double bd = (b.first+1)/(double)(b.second+1) - (b.first)/(double)b.second;
        return ad < bd;
    }
};

class Solution {
public:
    double maxAverageRatio(vector<vector<int>>& classes, int extraStudents) {
        double acc = 0;
        priority_queue<pair<int,int>, vector<pair<int,int>>, cmp> que;
        for(vector<int> i: classes)
            que.push(make_pair(i[0],i[1]));
        while(extraStudents--){
            pair<int,int> cur = que.top(); que.pop();
            cur.first++, cur.second++;
            que.push(cur);
        }
        while(!que.empty()){
            pair<int,int> cur = que.top(); que.pop();
            acc += cur.first / (double) cur.second;
        }
        return acc / (double) classes.size();
    }
};
/**
 * @param {number[][]} classes
 * @param {number} extraStudents
 * @return {number}
 */
class MaxHeap {
    constructor() {
        this.heap = [];
    }

    push(value) {
        this.heap.push(value);
        this.heapifyUp(this.heap.length - 1);
    }

    pop() {
        if (this.heap.length === 0) {
            return null;
        }
        if (this.heap.length === 1) {
            return this.heap.pop();
        }

        const top = this.heap[0];
        this.heap[0] = this.heap.pop();
        this.heapifyDown(0);

        return top;
    }

    heapifyUp(index) {
        while (index > 0) {
            const parent = Math.floor((index - 1) / 2);
            if (this.heap[parent][0] < this.heap[index][0]) {
                [this.heap[parent], this.heap[index]] = [this.heap[index], this.heap[parent]];
                index = parent;
            } else {
                break;
            }
        }
    }

    heapifyDown(index) {
        const n = this.heap.length;
        while (true) {
            let largest = index;
            const left = 2 * index + 1;
            const right = 2 * index + 2;

            if (left < n && this.heap[left][0] > this.heap[largest][0]) {
                largest = left;
            }
            if (right < n && this.heap[right][0] > this.heap[largest][0]) {
                largest = right;
            }

            if (largest !== index) {
                [this.heap[index], this.heap[largest]] = [this.heap[largest], this.heap[index]];
                index = largest;
            } else {
                break;
            }
        }
    }

    size() {
        return this.heap.length;
    }
}

var maxAverageRatio = function(classes, extraStudents) {
    const n = classes.length;

    // Helper function to calculate pass ratio increase
    const passRatioIncrease = (pass, total) => (pass + 1) / (total + 1) - pass / total;

    // Initialize max heap to keep track of classes with maximum improvement
    const maxHeap = new MaxHeap();

    for (let j = 0; j < n; j++) {
        const [pass, total] = classes[j];
        if (pass !== total) {
            const increase = passRatioIncrease(pass, total);
            maxHeap.push([increase, j]);
        }
    }

    let totalPassRatio = 0;

    for (let j = 0; j < n; j++) {
        totalPassRatio += classes[j][0] / classes[j][1];
    }

    for (let i = 0; i < extraStudents; i++) {
        if (maxHeap.size() === 0) {
            break; // No more classes to consider
        }

        const [increase, maxIndex] = maxHeap.pop();
        const [pass, total] = classes[maxIndex];
        const newPass = pass + 1;
        const newTotal = total + 1;
        const newIncrease = passRatioIncrease(newPass, newTotal);
        const newAvg = (totalPassRatio - (pass / total)) + (newPass / newTotal);

        if (newAvg <= totalPassRatio) {
            break; // No further improvement possible
        }

        totalPassRatio = newAvg;
        classes[maxIndex][0]++;
        classes[maxIndex][1]++;
        maxHeap.push([newIncrease, maxIndex]);
    }

    return totalPassRatio / n;
};
Maximum Average Pass Ratio