Ruby - Greedy, Priority Queue.
Observation\n\nIf there is a class with pass equeals p and total students equals t then pass ration equals p / t.\nAdding an extra student who passed exam incre
### Observation\n\nIf there is a class with pass equeals `p` and total students equals `t` then pass ration equals `p / t`.\nAdding an extra student who passed exam increases ration by:\n\n```\np + 1     p     (p + 1) * t - p * (t + 1)     t - p\n-----  -  - =  -------------------------- = -----------\nt + 1     t           t * (t + 1)           t * (t + 1) \n```\n\n### Solution\n\nIgnore classed where all students pass the exam (pass ration `1` cannot be increased).\nAll other store in a priority queue. Sort the queue by the increase ratio we can obtain by adding one extra student.\n\n```ruby\ndef max_average_ratio(classes, extra_students)\n  pq = classes.select { |p, t| p < t }.map { |p, t| [(t - p).to_f / (t * (t + 1)), p, t] }.sort\n  while pq.any? && (extra_students -= 1) >= 0\n    dr, p, t = pq.pop\n    ndr = dr * t / (t + 2) # new ratio increase. Same as (t - p) / ((t + 1) * (t + 2))\n\n    idx = pq.bsearch_index { |dr, _, _| dr >= ndr } || pq.size\n    pq.insert(idx, [ndr, p + 1, t + 1])\n  end\n  (pq.sum { |_, p, t| p.fdiv t } + classes.size - pq.size) / classes.size\nend\n```
['Ruby']