Formatted question description: https://leetcode.ca/all/1792.html

# 1792. Maximum Average Pass Ratio

## Level

Medium

## Description

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`

## Solution

Use a greedy approach. For each extra student, add the extra student to the class so that the class’ pass ratio increases the most. Use a priority queue to implement the greedy approach. After all extra students are added to the classes, calculate the average ratio and return.

```
class Solution {
public double maxAverageRatio(int[][] classes, int extraStudents) {
PriorityQueue<int[]> priorityQueue = new PriorityQueue<int[]>(new Comparator<int[]>() {
public int compare(int[] arr1, int[] arr2) {
long increase1Numerator = (long) arr1[1] - (long) arr1[0];
long increase1Denominator = (long) arr1[1] * (long) (arr1[1] + 1);
long increase2Numerator = (long) arr2[1] - (long) arr2[0];
long increase2Denominator = (long) arr2[1] * (long) (arr2[1] + 1);
long difference = increase2Numerator * increase1Denominator - increase1Numerator * increase2Denominator;
if (difference > 0)
return 1;
else if (difference < 0)
return -1;
else
return 0;
}
});
for (int[] arr : classes)
priorityQueue.offer(new int[]{arr[0], arr[1]});
for (int i = 0; i < extraStudents; i++) {
int[] arr = priorityQueue.poll();
int[] newArr = {arr[0] + 1, arr[1] + 1};
priorityQueue.offer(newArr);
}
double averageRatio = 0;
while (!priorityQueue.isEmpty()) {
int[] arr = priorityQueue.poll();
averageRatio += 1.0 * arr[0] / arr[1];
}
averageRatio /= classes.length;
return averageRatio;
}
}
```