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.
Example 1:
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.
Example 2:
Input: classes = [[2,4],[3,9],[4,5],[2,10]], extraStudents = 4
Output: 0.53485
Constraints:
1 <= classes.length <= 105classes[i].length == 21 <= passi <= totali <= 1051 <= extraStudents <= 105This approach uses a priority queue (or max heap) to determine which class will benefit the most from an extra student in terms of maximizing the pass ratio. The difference in pass ratio by adding an extra student is calculated for each class, and at each step, the student is added to the class with the maximum benefit.
Initially, calculate the potential pass ratio increase for one extra student to each class, insert these into the priority queue. Pop from the queue to get the class with maximum potential increase, add an extra student, calculate the new potential increase, and push it back to the queue. Repeat until all extra students are allocated.
The code utilizes a max heap to always pop the class that gains the most from an extra student. Each class's gain is defined as the change in pass ratio if an extra student is added. After processing all extra students, the average pass ratio is calculated and returned.
C++
Time Complexity: O((n + extraStudents) log n) where n is the number of classes.
Space Complexity: O(n) for storing classes in the heap.
This approach directly simulates the process of assigning extra students by iterating over each class and finding the gain for each possible allocation of extra students. Though less efficient, this is simpler and works within constraints when the number of classes or extra students is small.
The solution maintains a priority queue of class information using a custom comparator to prioritize classes that benefit the most from additional students. Each time a student is assigned, the ratios are recalculated.
JavaScript
Time Complexity: O((n + E) * log n), where E is the number of extraStudents.
Space Complexity: O(n) for storing ratios in the priority queue.
| Approach | Complexity |
|---|---|
| Approach 1: Greedy + Priority Queue | Time Complexity: O((n + extraStudents) log n) where n is the number of classes. Space Complexity: O(n) for storing classes in the heap. |
| Approach 2: Direct Simulation | Time Complexity: O((n + E) * log n), where E is the number of extraStudents. Space Complexity: O(n) for storing ratios in the priority queue. |
Maximum Average Pass Ratio | Detailed | Covered Minute Details | Leetcode 1792 | codestorywithMIK • codestorywithMIK • 7,957 views views
Watch 9 more video solutions →Practice Maximum Average Pass Ratio with our built-in code editor and test cases.
Practice on FleetCode