diff options
author | Jack Sangdahl <[email protected]> | 2024-12-14 19:36:16 -0700 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2024-12-14 19:36:16 -0700 |
commit | 879781c5dd20ac3fffec6567a296c6643c7403be (patch) | |
tree | 45406fcbb4948dff4b85bd7e9ec839059d4d224a /max_average_pass_ration.py | |
parent | 6454a6e0421beab63ae3eacb584ef68b9dbac564 (diff) | |
download | leetcode-879781c5dd20ac3fffec6567a296c6643c7403be.tar.gz leetcode-879781c5dd20ac3fffec6567a296c6643c7403be.zip |
1792. maximum average pass ratio
Diffstat (limited to 'max_average_pass_ration.py')
-rw-r--r-- | max_average_pass_ration.py | 41 |
1 files changed, 41 insertions, 0 deletions
diff --git a/max_average_pass_ration.py b/max_average_pass_ration.py new file mode 100644 index 0000000..b528ea6 --- /dev/null +++ b/max_average_pass_ration.py @@ -0,0 +1,41 @@ +# 1792. Maximum Average Pass Ratio +import heapq + +""" +there is a school that has classes of student 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 class, there are +'total_i' total students, but only 'pass_i' 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' to a class in a way that maximises the average pass ration +across all classes. return the maximum possible average pass ratio after +assigning the 'extraStudents'. 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 + """ + pq = [(a / b - (a + 1) / (b + 1), a, b) for a, b in classes] + heapq.heapify(pq) + while extraStudents: + v, a, b = heapq.heappop(pq) + a, b = a + 1, b + 1 + heapq.heappush(pq, (-(a + 1) / (b + 1) + a / b, a, b)) + extraStudents -= 1 + return sum(a / b for v, a, b in pq) / len(pq) + + +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) + ) |