1792. Maximum Average Pass Ratio (Leetcode)

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] = [pass_i, total_i]. You know beforehand that in the i^th class, there are total_i total students, but only pass_i 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.

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

Constraints:

• 1 <= classes.length <= 10 ^ 5
• classes[i].length == 2
• 1 <= pass_i <= total_i <= 10 ^ 5
• 1 <= extraStudents <= 10 ^ 5

Important Logic for solving this problem:

• In this problem we have to add 1 student at a time to any class to increase the overall pass ratio.
• Consider X to be ratio of the class before adding a brilliant student and let X' be the ratio of the class after adding a brilliant student.
• So difference between them can be calculated as... say dx = X' - X.
• Now you can clearly observe that the class with maximum dx should be selected at that particular iteration to maximize the overall ratio.
• Since we need to compare classes and find out the class giving maximum ratio difference (i.e dx), we will use PriorityQueue(MaxHeap).

Step by Step implementation:

• Create a comparator for comparing between two different classes. The class with greater dx will be chosen above the other.

Comparator<int[]> comp = new Comparator<>() { @Override public int compare(int[] a, int[] b) { double aBefore = (double) a[0] / (double) a[1]; double bBefore = (double) b[0] / (double) b[1]; double aAfter = (double) (a[0] + 1) / (double) (a[1] + 1); double bAfter = (double) (b[0] + 1) / (double) (b[1] + 1); double dxOfA = aAfter - aBefore; double dxOfB = bAfter - bBefore; return Double.compare(dxOfB, dxOfA); } };

• Create a priority-queue with the above created comparator. Add all classes to the priority-queue.

PriorityQueue<int[]> queue = new PriorityQueue<>(comp); for(int[] arr : classes) { queue.add(arr); }

• Add students one by one. For adding student pick out the class with maximum ratio(since it is max-heap the class with max ratio will be on top) and add 1 to its pass-value and total-value. This is because while adding a brilliant student the total number of students increases and also total passed students increases by 1.

while(extraStudents-- > 0) { int[] cur = queue.remove(); cur[0]++; cur[1]++; queue.add(cur); }

• After all students are added, take summation of all ratios of the classes and finally divide it by number of classes to get the overall result.

double sumOfRatios = 0; while(!queue.isEmpty()) { int[] cur = queue.remove(); sumOfRatios += (double) cur[0] / (double) cur[1]; } return sumOfRatios / (double) classes.length;

Full Code (Java): class Solution { public double maxAverageRatio(int[][] classes, int extraStudents) { // Step I Comparator<int[]> comp = new Comparator<>() { @Override public int compare(int[] a, int[] b) { double aBefore = (double) a[0] / (double) a[1]; double bBefore = (double) b[0] / (double) b[1]; double aAfter = (double) (a[0] + 1) / (double) (a[1] + 1); double bAfter = (double) (b[0] + 1) / (double) (b[1] + 1); double dxOfA = aAfter - aBefore; double dxOfB = bAfter - bBefore; // B written before A for sorting in descending order of ratio value return Double.compare(dxOfB, dxOfA); } }; // Step II PriorityQueue<int[]> queue = new PriorityQueue<>(comp); for(int[] arr : classes) { queue.add(arr); } // Step III while(extraStudents-- > 0) { int[] cur = queue.remove(); cur[0]++; cur[1]++; queue.add(cur); } // Step IV double sumOfRatios = 0; while(!queue.isEmpty()) { int[] cur = queue.remove(); sumOfRatios += (double) cur[0] / (double) cur[1]; } return sumOfRatios / (double) classes.length; } }