Simple py,JAVA code explaine din detail!! HEAP(Priority Queue) || Greedy
Problem understanding
They have given a list of list classes which contains pass and total of a class.idx[0] denotes the no of students who have passed the gina
# Problem understanding\n- They have given a list of list `classes` which contains `pass` and `total` of a class.`idx[0]` denotes the no of students who have passed the ginal exam and `idx[1]` total number of students in the the given ***class<sub>idx</sub>***.\n- They also given `extraStudents` which are *genius* students who are always capable of passing an exam.\n- we should add these `extraStudents` into `classes` such that the **avg pass ratio** is maximum.\n    - Note that `pass ratio` is ***pass<sub>i</sub>/total<sub>i</sub>***\n    - maximising class ratio is equivalent to that of maximising the average class ratio.\n--- \n# Hints\n- Read the 5 hints provided in the question!\n- Then try solving the problem on your own,if u still didn\'t get the hints properly try reading the solution.\n---\n# Approach:Heap+greedy\n<!-- Describe your approach to solving the problem. -->\n# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n- what we should observe is the `increase in pass ratio` or `gain` for each class after addition of 1 extra student.The one with highest `gain` gets the `1-extraStudent.`\n- This is calculated by `calculate_Increase_In_Pass_Ratio()` function,which tells what happen if current `pass`,`total` has the `1-extraStudent`.This is the *greedy startergy*.\n- We maintain a max-heap `heap` to manage this `gain`.The one with maximum `gain` gets the `extraStudent`.\n- So we allocate students`(extraStudent)` for the `class` with maximum `incInPassratio`.\n- First we have populated `heap` then we handled the above logic for 1-extraStudent per turn.\n- In the end we have calculate the totalSum named as `avg`(typo),then this total is divided by `classes` length to get the `maxAvg`.\n- This `maxAvg` is returned.\n\n# Complexity\n- Time complexity:$O(N)$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:$O(N)$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```Python3 []\nclass Solution:\n    def maxAverageRatio(self, classes: List[List[int]], extraStudents: int) -> float:\n        def calculate_Increase_In_Pass_Ratio(passes,total):\n            return ((passes+1)/(total+1))-(passes/total)\n        heap=[]\n        for p,t in classes:\n            heapq.heappush(heap,(-calculate_Increase_In_Pass_Ratio(p,t),p,t))\n        #print(list(heap))\n        for i in range(extraStudents):\n            _,p,t=heapq.heappop(heap)\n            heapq.heappush(heap,(-calculate_Increase_In_Pass_Ratio(p+1,t+1),p+1,t+1))\n        avg=0\n        #print(list(heap))\n        while heap:\n            _,p,t=heapq.heappop(heap)\n            avg+=p/t\n        return avg/len(classes)\n```\n```java []\nclass Solution {\n    public double calculateIncreaseInPassRatio(double pass,double total){\n        return ((double)(pass+1)/(total+1))-((double)pass/total);\n    }\n    public double maxAverageRatio(int[][] classes, int extraStudents) {\n        PriorityQueue<double[]> heap=new PriorityQueue<>((a,b)->Double.compare(b[0],a[0]));\n        for(int[] cl:classes){\n            double pass=cl[0],total=cl[1];\n            heap.offer(new double[]{calculateIncreaseInPassRatio(pass,total),pass,total});\n        }\n        for(int i=0;i<extraStudents;i++){\n            double[] top=heap.poll();\n            double pass=top[1],total=top[2];\n            heap.offer(new double[]{calculateIncreaseInPassRatio(pass+1,total+1),pass+1,total+1});\n        }\n        double avg=0;\n        while(!heap.isEmpty()){\n            double[] top=heap.poll();\n            double pass=top[1],total=top[2];\n            avg+=((double)pass)/total;\n        }\n        return avg/classes.length;\n    }\n}\n```
['Array', 'Greedy', 'Heap (Priority Queue)', 'Python', 'Java']