[Kotlin] Heap / Priority Queue solution (with comments)
Intuition / ApproachThe key to this problem is to greedily add students to the class which would benefit the most (i.e. would see the highest increase in pass r
# Intuition / Approach\n\nThe key to this problem is to greedily add students to the class which would benefit the most (i.e. would see the highest increase in pass ratio with this student) until no extra students remain. We can keep track of which class would see the highest increase by maintaining a heap / priority queue containing the indices of each class, sorted in descending order based on the delta in pass ratio after adding an extra student to that class.\n\n# Complexity\n- Time complexity: $$O((m+n)logn)$$, where $$m$$ is equal to `extraStudents` and $$n$$ is the size of `classes`\n\n- Space complexity: $$O(n)$$\n\n# Code\n```kotlin []\nclass Solution {\n    fun maxAverageRatio(classes: Array<IntArray>, extraStudents: Int): Double {\n\n        // Computes the positive delta in pass ratio after adding an extra student to classes[index]\n        fun computeDelta(index: Int): Double {\n            val pass: Int = classes[index][0]; val total: Int = classes[index][1]\n            return (pass + 1.0) / (total + 1.0) - (pass + 0.0) / (total + 0.0)\n        }\n\n        // Initialize PriorityQueue containing the indices of each class, sorted in descending order based \n        // on the delta in pass ratio after adding an extra student to that class.\n        val priorityQueue = PriorityQueue<Int>() { c1, c2 -> if (computeDelta(c2) < computeDelta(c1)) -1 else 1 }\n        for (index in classes.indices) {\n            priorityQueue.offer(index)\n        }\n\n        // Add students to the class which would benefit the most (i.e. would see the highest increase in \n        // pass ratio with this student) until no extra students remain.\n        var studentsRemaining: Int = extraStudents\n        while (studentsRemaining > 0) {\n            val head = priorityQueue.poll()\n\n            // Add extra student to this class\n            classes[head][0]++\n            classes[head][1]++\n\n            priorityQueue.offer(head)\n            studentsRemaining--\n        }\n\n        return priorityQueue.map({ index -> \n            classes[index][0].toDouble() / classes[index][1].toDouble() }).average()\n    }\n}\n```
['Greedy', 'Heap (Priority Queue)', 'Kotlin']