diff options
author | Jack Sangdahl <[email protected]> | 2025-09-01 11:31:14 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-09-01 11:31:14 -0600 |
commit | 926cb9384bf3b282310688d247cc245a444e62d4 (patch) | |
tree | 1522d8ec232991233c374818af243b164f8c4388 /maximum_average_pass_ratio.py | |
parent | c145fbb0137e61d512e38acab0a9444b43943647 (diff) | |
download | leetcode-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.py | 39 |
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) + ) |