Leetcode 1792: Maximum Average Pass Ratio
A school has several classes, and each class will have students taking a final exam. You are provided with a 2D array where each class is represented by two values: the number of students who will pass and the total number of students in the class. Additionally, a number of brilliant students, ’extraStudents,’ is provided. These brilliant students are guaranteed to pass if assigned to any class. The goal is to assign these extra students to maximize the average pass ratio of all classes. The pass ratio of a class is defined as the number of students passing divided by the total number of students in the class. You need to return the maximum possible average pass ratio after optimally distributing the extra students.
Problem
Approach
Steps
Complexity
Input: You are given a 2D array classes where each element classes[i] = [passi, totali], representing the number of students passing and the total number of students in the ith class. You are also given an integer extraStudents representing the number of extra students who can be assigned to any class to help improve the pass ratio.
Example: Input: classes = [[2, 5], [3, 6], [4, 8]], extraStudents = 3
Constraints:
• 1 <= classes.length <= 10^5
• classes[i].length == 2
• 1 <= passi <= totali <= 10^5
• 1 <= extraStudents <= 10^5
Output: Return the maximum possible average pass ratio after optimally assigning the extra students.
Example: Output: 0.72345
Constraints:
Goal: Maximize the average pass ratio by optimally assigning extra students to classes.
Steps:
• Calculate the initial pass ratio for each class.
• For each class, compute the potential gain in the pass ratio if one extra student is assigned.
• Use a priority queue to always assign extra students to the class with the highest potential gain in pass ratio.
• Repeat the process until all extra students are assigned.
• Return the average of the new pass ratios across all classes.
Goal: The input will always follow the specified constraints, ensuring the validity of the graph.
Steps:
• The number of classes will not exceed 10^5.
• Each class has at least one student and the total number of students in any class is at most 10^5.
• The number of extra students will be between 1 and 10^5.
Assumptions:
• All classes have a valid number of students, and the input data follows the format specified.
• Input: classes = [[2, 5], [3, 6], [4, 8]], extraStudents = 3
• Explanation: In this case, we can assign the extra students to the classes with the lowest initial pass ratios to maximize the average pass ratio.
• Input: classes = [[1, 2], [3, 5], [2, 2]], extraStudents = 2
• Explanation: Assigning the extra students to the first class will result in the highest increase in pass ratio.
Approach: To solve the problem, we need to assign the extra students to classes in a way that maximizes the overall average pass ratio. We can achieve this by calculating the potential gain for each class when an extra student is assigned and prioritizing classes that have the largest potential gain.
Observations:
• Each class has a different starting pass ratio.
• The potential improvement in pass ratio is greatest for classes with the lowest initial ratios.
• We need to calculate the gain from assigning extra students to each class and use a priority queue to select the class that would benefit the most from receiving an extra student.
Steps:
• Initialize a priority queue to keep track of the classes based on their potential gain from adding one extra student.
• For each class, calculate the potential gain from adding an extra student using the formula: (pass + 1) / (total + 1) - pass / total.
• Assign the extra students one by one to the class with the highest potential gain.
• After assigning all extra students, compute the average pass ratio of all the classes.
Empty Inputs:
• Empty input is not possible as per the problem constraints.
Large Inputs:
• The solution should be efficient enough to handle up to 10^5 classes and extra students.
Special Values:
• The classes and extra students are always within the specified constraints, so no special handling for negative values is needed.
Constraints:
• Classes will have at least one student, and the total students in each class will not exceed 10^5.
double maxAverageRatio(vector<vector<int>>& classes, int extraStudents) {
auto profit = [&](double pass, double total) {
return (pass + 1)/(total +1) -(pass/ total);
};
double total = 0;
priority_queue<pair<double, array<int, 2>>> pq;
for(auto &c: classes) {
total += (double) c[0]/c[1];
pq.push({profit(c[0], c[1]), {c[0], c[1]}});
}
while(extraStudents--) {
auto [addedProfit, c] = pq.top(); pq.pop();
total += addedProfit;
pq.push({profit(c[0] + 1, c[1] + 1), {c[0] +1, c[1] +1}});
}
return total/ classes.size();
}
1 : Function Definition
double maxAverageRatio(vector<vector<int>>& classes, int extraStudents) {
Define the function `maxAverageRatio` that takes a reference to a 2D vector `classes` and an integer `extraStudents`. The function returns a `double` representing the maximum average ratio of passing students after distributing the extra students.
2 : Lambda Function Definition
auto profit = [&](double pass, double total) {
Define a lambda function `profit` that calculates the improvement in the passing ratio when one extra student is added to a class. The improvement is computed using the formula `(pass + 1)/(total + 1) - (pass/total)`.
3 : Profit Calculation
return (pass + 1)/(total + 1) - (pass / total);
This line returns the profit of adding one extra student to the class, calculated by comparing the new passing ratio to the original ratio.
4 : Variable Initialization
double total = 0;
Initialize a variable `total` to accumulate the total passing ratio for all classes.
5 : Priority Queue Definition
priority_queue<pair<double, array<int, 2>>> pq;
Define a priority queue `pq` that will store pairs of profit values and class data (the number of passing and total students) to prioritize the classes that benefit the most from extra students.
6 : Loop Over Classes
for(auto &c: classes) {
Iterate over each class in the `classes` vector to calculate the initial passing ratio and store the profit of adding one student to each class.
7 : Total Passing Ratio Calculation
total += (double) c[0]/c[1];
Add the passing ratio for each class to the `total`. This is calculated by dividing the number of passing students `c[0]` by the total number of students `c[1]`.
8 : Push to Priority Queue
pq.push({profit(c[0], c[1]), {c[0], c[1]}});
Push the calculated profit and the class data (number of passing and total students) to the priority queue.
9 : While Loop for Extra Students
while(extraStudents--) {
Start a while loop that runs `extraStudents` times to distribute the extra students to the classes.
10 : Top Priority Class
auto [addedProfit, c] = pq.top(); pq.pop();
Get the class with the highest potential profit from adding an extra student, remove it from the priority queue.
11 : Update Total
total += addedProfit;
Update the `total` passing ratio by adding the profit of the class that received an extra student.
12 : Push Updated Class to Queue
pq.push({profit(c[0] + 1, c[1] + 1), {c[0] + 1, c[1] + 1}});
Push the updated class data (after adding one extra student) along with the new profit to the priority queue.
13 : Final Return
return total / classes.size();
Return the average passing ratio after distributing all extra students, calculated by dividing the total passing ratio by the number of classes.
Best Case: O(n log n), where n is the number of classes, as we perform operations related to the priority queue for each class and extra student.
Average Case: O(n log n), as the time complexity will depend on the number of classes and extra students.
Worst Case: O(n log n), due to the priority queue operations.
Description: The algorithm primarily depends on sorting and heap operations which take O(log n) time, making the overall complexity O(n log n).
Best Case: O(n), since we must store all classes in memory at once.
Worst Case: O(n), as we need space to store the classes and the priority queue.
Description: The space complexity is linear due to the storage of classes and the priority queue.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus