Beats 100% Users With 160ms Runtime || MAX HEAP.
IntuitionApproachComplexity
Time complexity:

Space complexity:
Code
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    double maxAverageRatio(vector<vector<int>>& classes, int extraStudents) {\n\n        int n = classes.size();\n        double total = 0;\n        // Create a heap to store the profit for each class along with the current pass and total student counts\n        vector<tuple<double, int, int>> heap;\n\n        // Populate the heap with initial values and calculate the total pass ratio\n        for (int i = 0; i < n; i++) \n        {\n            int pass = classes[i][0], totalStudents = classes[i][1];\n            // Add the pass ratio for the current class to the total\n            total += (double)pass / totalStudents;\n            // Calculate the potential increment in pass ratio by adding 1 extra student\n            heap.push_back(make_tuple(CalculateProfit(pass, totalStudents), pass, totalStudents));\n        }\n\n        // Build the heap to prioritize the class with the highest profit\n        MakeHeap(heap);\n\n        // Assign extra students to the classes with the highest potential profit\n        while (extraStudents-- > 0) \n        {\n            auto [maxIncrement, pass, totalStudents] = heap[0];\n\n            // If there is no increment possible, break\n            if (maxIncrement <= 0)\n            break;\n\n            total += maxIncrement;\n            pass++;\n            totalStudents++;\n            // Recalculate the new increment profit after adding a student\n            heap[0] = make_tuple(CalculateProfit(pass, totalStudents), pass, totalStudents);\n            // Reheapify the heap to maintain the heap property\n            HeapifyDown(heap, 0);\n        }\n\n        // Calculate and return the average pass ratio across all classes\n        return total / n;\n    }\n\nprivate:\n    // Calculate the profit, increase in pass ratio when adding a student to a class\n    double CalculateProfit(int pass, int total) {\n\n        double current_pass = (double)pass / total;\n        double new_pass = (double)(pass + 1) / (total + 1);\n\n        return new_pass - current_pass;\n    }\n\n    // Build the max heap by reheapifying from the bottom to the top\n    void MakeHeap(vector<tuple<double, int, int>>& heap) {\n\n        // Start from the last non-leaf node and heapify upwards\n        for (int i = heap.size() / 2 - 1; i >= 0; i--) \n        {\n            HeapifyDown(heap, i);\n        }\n    }\n\n    // Heapify the heap from index i downwards to ensure the heap property is maintained\n    void HeapifyDown(vector<tuple<double, int, int>>& heap, int i) {\n\n        int size = heap.size();\n\n        while (true) \n        {\n            int largest = i;\n            int left = 2 * i + 1;\n            int right = 2 * i + 2;\n\n            // If left child exists and has a larger increment\n            if (left < size && get<0>(heap[left]) > get<0>(heap[largest])) \n            {\n                largest = left;\n            }\n            // If right child exists and has a larger increment\n            if (right < size && get<0>(heap[right]) > get<0>(heap[largest])) \n            {\n                largest = right;\n            }\n            // If the largest value is already at i, the heap property is satisfied\n            if (largest == i)\n            break;\n\n            // Swap the current node with the largest child\n            swap(heap[i], heap[largest]);\n            // Move to the child\n            i = largest;\n        }\n    }\n};\n```
['C++']