1792. Maximum Average Pass Ratio

How to solve Maximum Average Pass Ratio (LeetCode 1792): the approach in brief

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]. You know beforehand that in the ith class, there are totali total students, but only passi number of students will pass the exam.

Pattern

Maximum Average Pass Ratio is a Heap (Priority Queue) Patterns problem, in the Scheduling / Minimum Cost (Greedy with Priority Queue) subpattern. The pattern covers top K elements, K-way merge, two heaps for median, and scheduling

Solve scheduling and optimization problems using priority queue with greedy approach.

Approach outline

1. Pay attention to how much the pass ratio changes when you add a student to the class. If you keep adding students, what happens to the change in pass ratio? The more students you add to a class, the smaller the change in pass ratio becomes.
2. Since the change in the pass ratio is always decreasing with the more students you add, then the very first student you add to each class is the one that makes the biggest change in the pass ratio.
3. Because each class's pass ratio is weighted equally, it's always optimal to put the student in the class that makes the biggest change among all the other classes.

Complexity

The reference solution runs in O((n + extraStudents) * log n) time and O(n) space.

Asked at

Maximum Average Pass Ratio has been reported in interviews at Amazon.