MediumNo. 1792
Maximum Average Pass Ratio — LeetCode 1792 Python Solution
- Pattern
- Heap / Priority Queue
- Topics
- Greedy, Array, Heap (Priority Queue)
- Reading time
- 2 min
- Source
- leetcode.com
The problem
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].
Example
- 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.
Python solution
class Solution:
def maxAverageRatio(self, classes: List[List[int]], extraStudents: int) -> float:
h = [(a / b - (a + 1) / (b + 1), a, b) for a, b in classes]
heapify(h)
for _ in range(extraStudents):
_, a, b = heappop(h)
a, b = a + 1, b + 1
heappush(h, (a / b - (a + 1) / (b + 1), a, b))
return sum(v[1] / v[2] for v in h) / len(classes)Complexity
- Time
- O(n × log n)
- Space · auxiliary
- O(n)
Pattern: Heap / Priority Queue
Keep only the best k elements, or always pull the smallest, in log time. LeetCode 1792. Maximum Average Pass Ratio is filed here because LeetCode tags it Heap (Priority Queue), which is the vocabulary this hub collects.
The heap / priority queue guide has the Python template for the pattern and the 163 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0502 | IPO | Hard |
| 0630 | Course Schedule III | Hard |
| 0857 | Minimum Cost to Hire K Workers | Hard |
| 1353 | Maximum Number of Events That Can Be Attended | Medium |
| 1383 | Maximum Performance of a Team | Hard |
| 1642 | Furthest Building You Can Reach | Medium |
Frequently asked questions
- How hard is LeetCode 1792. Maximum Average Pass Ratio?
LeetCode 1792. Maximum Average Pass Ratio is rated Medium on LeetCode.
- What is the time complexity of LeetCode 1792. Maximum Average Pass Ratio?
The Python solution on this page runs in O(n × log n).
- What is the space complexity of LeetCode 1792. Maximum Average Pass Ratio?
The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 1792. Maximum Average Pass Ratio cover?
LeetCode 1792. Maximum Average Pass Ratio is tagged Greedy, Array and Heap (Priority Queue) on LeetCode.