Maximum average pass ratio

Array Greedy Heap (Priority Queue)

74.1% acceptance

Feb 25, 2026

1931

139

There is a school that has classes of students and each class will be having a final exam. classes[i] = [pass, total]. extraStudents brilliant students are guaranteed to pass any class. Maximize the average pass ratio.

Solution

Rust

Time O(n log n)

Space O(n)

LeetCode

solution.rs

use std::collections::BinaryHeap;
use std::cmp::Ordering;

#[derive(PartialEq)]
struct F64(f64);
impl Eq for F64 {}
impl PartialOrd for F64 {
  fn partial_cmp(&self, other: &Self) -> Option<Ordering> { self.0.partial_cmp(&other.0) }
}
impl Ord for F64 {
  fn cmp(&self, other: &Self) -> Ordering { self.partial_cmp(other).unwrap_or(Ordering::Equal) }
}

impl Solution {
  pub fn max_average_ratio(classes: Vec<Vec<i32>>, extra_students: i32) -> f64 {
    let gain = |p: f64, t: f64| (p + 1.0) / (t + 1.0) - p / t;
    let mut heap: BinaryHeap<(F64, i32, i32)> = classes.iter()
      .map(|c| (F64(gain(c[0] as f64, c[1] as f64)), c[0], c[1]))
      .collect();
    for _ in 0..extra_students {
      let (_, p, t) = heap.pop().unwrap();
      let (p, t) = (p + 1, t + 1);
      heap.push((F64(gain(p as f64, t as f64)), p, t));
    }
    let sum: f64 = heap.iter().map(|(_, p, t)| *p as f64 / *t as f64).sum();
    sum / heap.len() as f64
  }
}