aboutsummaryrefslogtreecommitdiff
path: root/maximum_average_pass_ratio.py
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-09-01 11:31:14 -0600
committerJack Sangdahl <[email protected]>2025-09-01 11:31:14 -0600
commit926cb9384bf3b282310688d247cc245a444e62d4 (patch)
tree1522d8ec232991233c374818af243b164f8c4388 /maximum_average_pass_ratio.py
parentc145fbb0137e61d512e38acab0a9444b43943647 (diff)
downloadleetcode-926cb9384bf3b282310688d247cc245a444e62d4.tar.gz
leetcode-926cb9384bf3b282310688d247cc245a444e62d4.zip
1792. maximum average pass ratio
Diffstat (limited to 'maximum_average_pass_ratio.py')
-rw-r--r--maximum_average_pass_ratio.py39
1 files changed, 39 insertions, 0 deletions
diff --git a/maximum_average_pass_ratio.py b/maximum_average_pass_ratio.py
new file mode 100644
index 0000000..41aa9fa
--- /dev/null
+++ b/maximum_average_pass_ratio.py
@@ -0,0 +1,39 @@
+# 1792. Maximum Average Pass Ratio
+import heapq
+
+"""
+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] =
+[pass_i, total_i]'. you know beforehand that in the i'th there are 'total_i'
+students, but only 'pass_i' students that will pass the exam. you are also
+given in integer 'extraStudents'. there are another 'extraStudents' brilliant
+students that are guaranteed to pass the exam of any class. return the
+maximum possible average pass ratio after assigning the 'extraStudents'
+students. answers within 10^-5 of the actual answer will be accepted.
+"""
+
+
+class Solution(object):
+ def maxAverageRatio(self, classes, extraStudents):
+ """
+ :type classes: List[List[int]]
+ :type extraStudents: int
+ :rtype: float
+ """
+ h = [(a / b - (a + 1) / (b + 1), a, b) for a, b in classes]
+ heapq.heapify(h)
+ while extraStudents:
+ v, a, b = heapq.heappop(h)
+ a += 1
+ b += 1
+ heapq.heappush(h, (-(a + 1) / (b + 1) + a / b, a, b))
+ extraStudents -= 1
+ return sum(a / b for v, a, b in h) / len(h)
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.maxAverageRatio(classes=[[1, 2], [3, 5], [2, 2]], extraStudents=2))
+ print(
+ obj.maxAverageRatio(classes=[[2, 4], [3, 9], [4, 5], [2, 10]], extraStudents=4)
+ )