Search⌘ K
AI Features
Home
Courses
Grokking the Coding Interview Patterns in Python

Solution: Maximum Average Pass Ratio

Explore how to apply a greedy algorithm with max heaps to maximize the average pass ratio in multiple classes by strategically assigning extra students. Understand the calculation of gains, heap operations, and the overall approach to solving this dynamic optimization problem efficiently using Python. The lesson provides insights into managing tradeoffs in time complexity and practical coding patterns for interview preparedness.

We'll cover the following...

Statement

A school has several classes of students, each taking a final exam. You are provided a 2D integer array, classes, where classes[i] = [passi, totali]. Here, passi represents the number of students in the ithi^{th} class who are expected to pass the exam, and totali represents the total number of students in that class.

Additionally, you are given an integer, extraStudents, which denotes the number of brilliant extra students guaranteed to pass their exams. These students can be assigned to any class, and your goal is to distribute them to maximize the average pass ratio across all classes.

The pass ratio for a class is defined as the ratio of the number of students passing to the total number of students in the class:

The average pass ratio is the sum of the pass ratios of all classes divided by the total number of classes:

Your task is to return the maximum achievable average pass ratio after assigning all extraStudents to the classes. Answers within 10−510^{-5} of the actual answer will be accepted.

Constraints:

  • 1≤1 \leq classes.length ≤103\leq 10^3 ...