Maximum Average Pass ratio

XXX. Maximize Class Average After Adding Students

Priority Queue

Greedy Algorithm

Problem Statement:

You are given a 2D integer array classes, where classes[i] = [passi, totali] indicates the number of students who passed and the total number of students in the ith class. You are also given an integer extraStudents, the number of additional students you can distribute to any class.

Your goal is to maximize the overall average pass ratio after distributing the extra students optimally. The pass ratio for a class is defined as passi / totali.

Algorithm:

1. Use a Priority Queue:

   Maintain a priority queue to select the class where adding an extra student provides the maximum marginal increase in the pass ratio. The priority is determined by the difference between the current ratio and the ratio after adding an extra student.

2. Distribute Extra Students:

   For each of the extra students, extract the class with the highest marginal benefit from the priority queue, update its pass and total counts, and reinsert it into the queue.

3. Calculate the Final Average:

   Sum up the pass ratios of all classes and divide by the total number of classes to obtain the final average.

Complexity:

Time Complexity: O((n + extraStudents) log n), where n is the number of classes and log n accounts for the heap operations.
Space Complexity: O(n), due to the priority queue storage.

Java Implementation:

class Solution {
    public double maxAverageRatio(int[][] classes, int extraStudents) {
        // Priority queue sorted by marginal benefit
        PriorityQueue pq = new PriorityQueue<>((a, b) -> 
            Double.compare(
                ((double) (b[0] + 1) / (b[1] + 1)) - ((double) b[0] / b[1]),
                ((double) (a[0] + 1) / (a[1] + 1)) - ((double) a[0] / a[1])
            )
        );

        // Add all classes to the priority queue
        for (int[] c : classes) 
            pq.add(c);
        

        // Distribute extra students
        while (extraStudents > 0) {
            int[] curr = pq.poll();
            curr[0]++;  // Increment pass count
            curr[1]++;  // Increment total students
            extraStudents--;
            pq.add(curr);  // Reinsert class with updated ratio
        }

        // Calculate the final average
        double totalOverall = 0;
        for (int[] c : classes) 
            totalOverall += (double) c[0] / c[1];
        

        return totalOverall / classes.length;
    }
}