Maximum Average Pass Ratio

Explore how to maximize the average pass ratio across multiple classes by distributing extra students strategically. Learn to apply heap data structures to solve this dynamic optimization problem efficiently. Understand the problem constraints, develop a clear approach, and implement the solution in a coding environment to master this common interview challenge.

We'll cover the following...

Statement
Examples
Understand the problem
Figure it out!
Try it yourself

Statement

A school has several classes of students, each taking a final exam. You are provided a 2D integer array, classes, where classes[i] = [passi, totali]. Here, passi represents the number of students in the $i^{th}$ class who are expected to pass the exam, and totali represents the total number of students in that class.

Additionally, you are given an integer, extraStudents, which denotes the number of brilliant extra students guaranteed to pass their exams. These students can be assigned to any class, and your goal is to distribute them to maximize the average pass ratio across all classes.

The pass ratio for a class is defined as the ratio of the number of students passing to the total number of students in the class: