# Maximum Average Pass Ratio
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-average-pass-ratio)
Canonical: https://scaleengineer.com/dsa/problems/maximum-average-pass-ratio
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** Array, Heap (Priority Queue)
---
## Problem
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.

**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 <= 105`
* `classes[i].length == 2`
* `1 <= passi <= totali <= 105`
* `1 <= extraStudents <= 105`

# Approaches
## Brute Force Simulation
This approach simulates the process directly. For each of the `extraStudents`, it iterates through all the classes to find the one that would yield the highest increase in pass ratio if the student were added to it. After finding the best class, it updates that class's student counts and repeats the process for the next student.
**Time:** O(k * n), where `k` is `extraStudents` and `n` is `classes.length`. For each of the `k` students, we perform a linear scan of `n` classes to find the best one to update. · **Space:** O(n), where `n` is the number of classes. This is for storing a mutable copy of the classes data. If the input array is modified in-place, the space complexity would be O(1).
**Pros:** Simple to understand and implement.; Correctly follows the greedy logic without complex data structures.
**Cons:** Highly inefficient due to the repeated linear scan of all classes for each extra student.; Will result in a "Time Limit Exceeded" error on platforms like LeetCode for the given constraints.
### Explanation
The core idea is a greedy one: at each step, make the locally optimal choice. The best choice for placing one student is to add them to the class where the gain in the pass ratio is maximized. This approach implements this greedy strategy in the most straightforward way, by repeatedly searching for the best class to augment.

```java
class Solution {
    public double maxAverageRatio(int[][] classes, int extraStudents) {
        int n = classes.length;
        // Create a copy to modify, using doubles for precision
        double[][] currentClasses = new double[n][2];
        for (int i = 0; i < n; i++) {
            currentClasses[i][0] = classes[i][0];
            currentClasses[i][1] = classes[i][1];
        }

        // Distribute each extra student one by one
        for (int i = 0; i < extraStudents; i++) {
            int bestClassIndex = -1;
            double maxIncrease = -1.0;

            // Find the class that gives the maximum increase in ratio
            for (int j = 0; j < n; j++) {
                double pass = currentClasses[j][0];
                double total = currentClasses[j][1];
                
                // Calculate the increase in ratio if one student is added.
                double increase = (pass + 1) / (total + 1) - pass / total;

                if (increase > maxIncrease) {
                    maxIncrease = increase;
                    bestClassIndex = j;
                }
            }
            
            // Add the student to the best class found
            if (bestClassIndex != -1) {
                currentClasses[bestClassIndex][0]++;
                currentClasses[bestClassIndex][1]++;
            }
        }

        // Calculate the final average ratio
        double totalRatioSum = 0;
        for (int i = 0; i < n; i++) {
            totalRatioSum += currentClasses[i][0] / currentClasses[i][1];
        }

        return totalRatioSum / n;
    }
}
```
### Algorithm
- Create a mutable copy of the `classes` array, using `double` to maintain precision.
- Loop `extraStudents` times.
- In each iteration of the loop, find the best class to update:
  - Initialize `maxIncrease` to a very small number and `bestClassIndex` to -1.
  - Iterate through all classes. For each class, calculate the potential increase in its pass ratio if one student is added. The increase is `(pass + 1) / (total + 1) - pass / total`.
  - If this increase is greater than `maxIncrease`, update `maxIncrease` and `bestClassIndex`.
- After scanning all classes, add one student to the class at `bestClassIndex` by incrementing its pass and total counts.
- After the main loop finishes, calculate the sum of the final pass ratios of all classes.
- Return the sum divided by the total number of classes.

## Greedy Approach with Max-Heap
This approach optimizes the greedy strategy by using a max-heap (Priority Queue). Instead of repeatedly scanning all classes to find the one with the maximum potential ratio increase, we store all classes in a max-heap prioritized by this increase. This allows us to find the best class in logarithmic time instead of linear time, making the solution efficient enough for the given constraints.
**Time:** O((n + k) * log n), where `k` is `extraStudents` and `n` is `classes.length`. Building the heap takes `O(n * log n)`. Then, for each of the `k` students, we perform one poll and one offer operation, each taking `O(log n)` time. · **Space:** O(n), to store all `n` classes in the max-heap.
**Pros:** Highly efficient, passing all test cases within the time limit.; Optimal greedy approach for this problem.
**Cons:** More complex to implement than the brute-force approach due to the use of a heap.; Requires extra space for the heap.
### Explanation
The key observation is that the brute-force approach is slow because of the repeated search for the maximum increase. A max-heap is the ideal data structure to efficiently retrieve the maximum element at each step.

We define the "priority" of a class as the gain in pass ratio we get by adding one extra student. This gain, `delta`, is calculated as `(p + 1) / (t + 1) - p / t`, which simplifies to the more numerically stable formula `(t - p) / (t * (t + 1))`. By storing classes in a max-heap ordered by this `delta`, we can always access the most beneficial class to update in `O(log n)` time.

```java
import java.util.PriorityQueue;

class Solution {
    public double maxAverageRatio(int[][] classes, int extraStudents) {
        int n = classes.length;
        // Max-heap to store classes, ordered by the potential increase in pass ratio.
        // The element is a double array: {increase, pass, total}
        PriorityQueue<double[]> pq = new PriorityQueue<>((a, b) -> Double.compare(b[0], a[0]));

        for (int[] c : classes) {
            double pass = c[0];
            double total = c[1];
            // The increase is (t - p) / (t * (t + 1))
            double increase = (total - pass) / (total * (total + 1));
            pq.offer(new double[]{increase, pass, total});
        }

        // Distribute the extra students
        for (int i = 0; i < extraStudents; i++) {
            double[] current = pq.poll();
            double pass = current[1] + 1;
            double total = current[2] + 1;
            
            // Calculate the new potential increase for this class
            double newIncrease = (total - pass) / (total * (total + 1));
            pq.offer(new double[]{newIncrease, pass, total});
        }

        // Calculate the total average ratio
        double totalRatioSum = 0;
        while (!pq.isEmpty()) {
            double[] c = pq.poll();
            totalRatioSum += c[1] / c[2];
        }

        return totalRatioSum / n;
    }
}
```
### Algorithm
- Initialize a max-heap (like Java's `PriorityQueue` with a custom comparator) to store class information, prioritized by the potential ratio increase.
- For each class `c = [pass, total]` in the input:
  - Calculate the initial ratio increase `delta = (total - pass) / (total * (total + 1))`.
  - Add an object or array representing the class, like `{delta, pass, total}`, to the max-heap.
- Loop `extraStudents` times:
  - Extract the element with the maximum `delta` from the heap. This represents the class that gives the best improvement.
  - Update its counts: `new_pass = pass + 1`, `new_total = total + 1`.
  - Recalculate the `new_delta` for this updated class.
  - Add the updated class information back to the heap.
- After the loop, the heap contains the final configurations of all classes.
- Initialize `total_ratio_sum = 0`.
- While the heap is not empty, extract each class, calculate its ratio `pass / total`, and add it to `total_ratio_sum`.
- Return `total_ratio_sum / number of classes`.

# Solutions
### Java

```java
class Solution {
public
  double maxAverageRatio(int[][] classes, int extraStudents) {
    PriorityQueue<double[]> pq = new PriorityQueue<>((a, b)->{
      double x = (a[0] + 1) / (a[1] + 1) - a[0] / a[1];
      double y = (b[0] + 1) / (b[1] + 1) - b[0] / b[1];
      return Double.compare(y, x);
    });
    for (var e : classes) {
      pq.offer(new double[]{e[0], e[1]});
    }
    while (extraStudents-- > 0) {
      var e = pq.poll();
      double a = e[0] + 1, b = e[1] + 1;
      pq.offer(new double[]{a, b});
    }
    double ans = 0;
    while (!pq.isEmpty()) {
      var e = pq.poll();
      ans += e[0] / e[1];
    }
    return ans / classes.length;
  }
}

```

### CPP

```cpp
class Solution {
public:
  double maxAverageRatio(vector<vector<int>> &classes, int extraStudents) {
    priority_queue<tuple<double, int, int>> pq;
    for (auto &e : classes) {
      int a = e[0], b = e[1];
      double x = (double)(a + 1) / (b + 1) - (double)a / b;
      pq.push({x, a, b});
    }
    while (extraStudents--) {
      auto [_, a, b] = pq.top();
      pq.pop();
      a++;
      b++;
      double x = (double)(a + 1) / (b + 1) - (double)a / b;
      pq.push({x, a, b});
    }
    double ans = 0;
    while (pq.size()) {
      auto [_, a, b] = pq.top();
      pq.pop();
      ans += (double)a / b;
    }
    return ans / classes.size();
  }
};

```

### Python

```python
class Solution:
    def maxAverageRatio(self, classes: List[List[int]], extraStudents: int) -> float: h = [(a / b - (a + 1) / (b + 1), a, b) for a, b in classes] heapify(h) for _ in range(extraStudents): _, a, b = heappop(h) a, b = a + 1, b + 1 heappush(h, (a / b - (a + 1) / (b + 1), a, b)) return sum(v[1] / v[2] for v in h) / len(classes)

```