1792. Maximum Average Pass Ratio LeetCode Solution
In this guide, you will get 1792. Maximum Average Pass Ratio LeetCode Solution with the best time and space complexity. The solution to Maximum Average Pass Ratio problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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.
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.
Time Complexity: O((|\texttt{classes}| + |\texttt{extraStudents}|) \log |\texttt{classes}|)
Space Complexity: O(|\texttt{classes}|)
1792. Maximum Average Pass Ratio LeetCode Solution in C++
class Solution {
public:
double maxAverageRatio(vector<vector<int>>& classes, int extraStudents) {
// (extra pass ratio, pass, total)
priority_queue<tuple<double, int, int>> maxHeap;
for (const vector<int>& c : classes) {
const int pass = c[0];
const int total = c[1];
maxHeap.emplace(extraPassRatio(pass, total), pass, total);
}
for (int i = 0; i < extraStudents; ++i) {
const auto [_, pass, total] = maxHeap.top();
maxHeap.pop();
maxHeap.emplace(extraPassRatio(pass + 1, total + 1), pass + 1, total + 1);
}
double ratioSum = 0;
while (!maxHeap.empty()) {
const auto [_, pass, total] = maxHeap.top();
maxHeap.pop();
ratioSum += pass / static_cast<double>(total);
}
return ratioSum / classes.size();
}
private:
// Returns the extra pass ratio if a brilliant student joins.
double extraPassRatio(int pass, int total) {
return (pass + 1) / static_cast<double>(total + 1) -
pass / static_cast<double>(total);
}
}; /* code provided by PROGIEZ */
1792. Maximum Average Pass Ratio LeetCode Solution in Java
class Solution {
public double maxAverageRatio(int[][] classes, int extraStudents) {
// (extra pass ratio, pass, total)
PriorityQueue<T> maxHeap =
new PriorityQueue<>((a, b) -> Double.compare(b.extraPassRatio, a.extraPassRatio));
for (int[] c : classes) {
final int pass = c[0];
final int total = c[1];
maxHeap.offer(new T(getExtraPassRatio(pass, total), pass, total));
}
for (int i = 0; i < extraStudents; ++i) {
final int pass = maxHeap.peek().pass;
final int total = maxHeap.poll().total;
maxHeap.offer(new T(getExtraPassRatio(pass + 1, total + 1), pass + 1, total + 1));
}
double ratioSum = 0;
while (!maxHeap.isEmpty())
ratioSum += maxHeap.peek().pass / (double) maxHeap.poll().total;
return ratioSum / classes.length;
}
// Returns the extra pass ratio if a brilliant student joins.
private double getExtraPassRatio(int pass, int total) {
return (pass + 1) / (double) (total + 1) - pass / (double) total;
}
private record T(double extraPassRatio, int pass, int total){};
} // code provided by PROGIEZ
1792. Maximum Average Pass Ratio LeetCode Solution in Python
class Solution:
def maxAverageRatio(
self,
classes: list[list[int]],
extraStudents: int,
) -> float:
def extraPassRatio(pas: int, total: int) -> float:
"""Returns the extra pass ratio if a brilliant student joins."""
return (pas + 1) / (total + 1) - pas / total
maxHeap = [(-extraPassRatio(pas, total), pas, total)
for pas, total in classes]
heapq.heapify(maxHeap)
for _ in range(extraStudents):
_, pas, total = heapq.heappop(maxHeap)
heapq.heappush(
maxHeap, (-extraPassRatio(pas + 1, total + 1), pas + 1, total + 1))
return sum(pas / total for _, pas, total in maxHeap) / len(maxHeap) # code by PROGIEZ
