You are given a list of classes, where each class has pass_i students who have passed and total_i total students. You are also given an integer extraStudents representing the number of extra students you can assign to any class (one at a time, possibly to the same class multiple times). When an extra student is assigned to a class, both pass_i and total_i for that class increase by 1 (the extra student always passes).
Your goal is to maximize the average pass ratio across all classes after assigning all extra students. The pass ratio for a class is pass_i / total_i, and the average pass ratio is the sum of all class pass ratios divided by the number of classes.
Constraints include:
At first glance, you might think to distribute the extra students evenly across all classes. However, not all classes benefit equally from an extra passing student. For some classes, adding a student increases their pass ratio significantly, while for others, the gain is minimal.
The key insight is to always assign the next extra student to the class where they will have the biggest possible increase in average pass ratio. This requires calculating, for each class, how much its pass ratio would increase if we gave it one more passing student. To do this efficiently, we need a way to always pick the class with the highest potential gain.
This leads us to use a greedy algorithm, where at each step we assign the next student to the class with the largest marginal increase in pass ratio.
pass_i / total_i(pass_i + 1) / (total_i + 1)((pass_i + 1) / (total_i + 1)) - (pass_i / total_i)pass_i and total_i by 1pass_i / total_i for all classes, divided by the number of classes.
total_i increases.
Input: classes = [[1,2],[3,5],[2,2]], extraStudents = 2
The Maximum Average Pass Ratio problem rewards a greedy strategy: always assign the next extra passing student to the class where their impact is greatest. By using a max-heap to efficiently track and update the best candidate class for each assignment, we ensure optimal distribution of extra students. This approach is both efficient and elegant, making the most out of every extra student to maximize the overall average pass ratio.
import heapq
class Solution:
def maxAverageRatio(self, classes, extraStudents):
# Function to calculate the marginal gain
def gain(p, t):
return (p + 1) / (t + 1) - p / t
# Max heap, store (-gain, p, t)
heap = []
for p, t in classes:
heapq.heappush(heap, (-gain(p, t), p, t))
for _ in range(extraStudents):
neg_g, p, t = heapq.heappop(heap)
p += 1
t += 1
heapq.heappush(heap, (-gain(p, t), p, t))
total = 0
for _, p, t in heap:
total += p / t
return total / len(classes)
#include <vector>
#include <queue>
using namespace std;
class Solution {
public:
double maxAverageRatio(vector<vector<int>>& classes, int extraStudents) {
auto gain = [](int p, int t) {
return ((double)(p + 1) / (t + 1)) - ((double)p / t);
};
// max heap: pair<gain, pair<p, t>>
priority_queue<pair<double, pair<int, int>>> heap;
for (auto& c : classes) {
heap.push({gain(c[0], c[1]), {c[0], c[1]}});
}
for (int i = 0; i < extraStudents; ++i) {
auto top = heap.top(); heap.pop();
int p = top.second.first, t = top.second.second;
++p; ++t;
heap.push({gain(p, t), {p, t}});
}
double total = 0;
while (!heap.empty()) {
auto top = heap.top(); heap.pop();
int p = top.second.first, t = top.second.second;
total += (double)p / t;
}
return total / classes.size();
}
};
import java.util.PriorityQueue;
class Solution {
public double maxAverageRatio(int[][] classes, int extraStudents) {
PriorityQueue<double[]> heap = new PriorityQueue<>((a, b) -> Double.compare(b[0], a[0]));
for (int[] c : classes) {
double gain = ((double)(c[0] + 1) / (c[1] + 1)) - ((double)c[0] / c[1]);
heap.offer(new double[]{gain, c[0], c[1]});
}
for (int i = 0; i < extraStudents; i++) {
double[] top = heap.poll();
int p = (int)top[1] + 1;
int t = (int)top[2] + 1;
double gain = ((double)(p + 1) / (t + 1)) - ((double)p / t);
heap.offer(new double[]{gain, p, t});
}
double total = 0;
while (!heap.isEmpty()) {
double[] c = heap.poll();
total += (double)c[1] / c[2];
}
return total / classes.length;
}
}
class MaxHeap {
constructor() {
this.data = [];
}
push(val) {
this.data.push(val);
this._bubbleUp();
}
pop() {
if (this.data.length === 1) return this.data.pop();
const top = this.data[0];
this.data[0] = this.data.pop();
this._bubbleDown();
return top;
}
_bubbleUp() {
let idx = this.data.length - 1;
while (idx > 0) {
let parent = Math.floor((idx - 1) / 2);
if (this.data[idx][0] <= this.data[parent][0]) break;
[this.data[idx], this.data[parent]] = [this.data[parent], this.data[idx]];
idx = parent;
}
}
_bubbleDown() {
let idx = 0;
let length = this.data.length;
while (true) {
let left = 2 * idx + 1, right = 2 * idx + 2, largest = idx;
if (left < length && this.data[left][0] > this.data[largest][0]) largest = left;
if (right < length && this.data[right][0] > this.data[largest][0]) largest = right;
if (largest === idx) break;
[this.data[idx], this.data[largest]] = [this.data[largest], this.data[idx]];
idx = largest;
}
}
size() {
return this.data.length;
}
}
var maxAverageRatio = function(classes, extraStudents) {
function gain(p, t) {
return (p + 1) / (t + 1) - p / t;
}
let heap = new MaxHeap();
for (let [p, t] of classes) {
heap.push([gain(p, t), p, t]);
}
for (let i = 0; i < extraStudents; ++i) {
let [g, p, t] = heap.pop();
p += 1; t += 1;
heap.push([gain(p, t), p, t]);
}
let total = 0;
while (heap.size() > 0) {
let [_, p, t] = heap.pop();
total += p / t;
}
return total / classes.length;
};