Minimum Cost to Hire K Workers

class Solution {
public:
    double mincostToHireWorkers(vector<int>& quality, vector<int>& wage, int k) {
        int n = quality.size();
        vector<pair<double,int>> w(n);
        for (int i = 0; i < n; ++i) w[i] = {(double)wage[i] / quality[i], quality[i]};
        sort(w.begin(), w.end());
        priority_queue<int> pq;
        int sumQ = 0;
        double best = 1e18;
        for (auto& [r, q] : w) {
            sumQ += q;
            pq.push(q);
            if ((int)pq.size() > k) { sumQ -= pq.top(); pq.pop(); }
            if ((int)pq.size() == k) best = min(best, sumQ * r);
        }
        return best;
    }
};

type intMaxHeap []int

func (h intMaxHeap) Len() int            { return len(h) }
func (h intMaxHeap) Less(i, j int) bool  { return h[i] > h[j] }
func (h intMaxHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *intMaxHeap) Push(x interface{}) { *h = append(*h, x.(int)) }
func (h *intMaxHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[:n-1]
    return x
}

func mincostToHireWorkers(quality []int, wage []int, k int) float64 {
    n := len(quality)
    type pair struct {
        ratio float64
        q     int
    }
    w := make([]pair, n)
    for i := 0; i < n; i++ {
        w[i] = pair{float64(wage[i]) / float64(quality[i]), quality[i]}
    }
    sort.Slice(w, func(i, j int) bool { return w[i].ratio < w[j].ratio })
    h := &intMaxHeap{}
    sumQ := 0
    best := math.MaxFloat64
    for _, p := range w {
        sumQ += p.q
        heap.Push(h, p.q)
        if h.Len() > k {
            sumQ -= heap.Pop(h).(int)
        }
        if h.Len() == k {
            if cost := float64(sumQ) * p.ratio; cost < best {
                best = cost
            }
        }
    }
    return best
}

from typing import List
import heapq

class Solution:
    def mincostToHireWorkers(self, quality: List[int], wage: List[int], k: int) -> float:
        n = len(quality)
        w = sorted([(wage[i] / quality[i], quality[i]) for i in range(n)])
        heap = []  # max-heap via negation
        sum_q = 0
        best = float('inf')
        for ratio, q in w:
            sum_q += q
            heapq.heappush(heap, -q)
            if len(heap) > k:
                sum_q += heapq.heappop(heap)  # pop is negative of largest
            if len(heap) == k:
                best = min(best, sum_q * ratio)
        return best

class MaxHeap {
    constructor() { this.h = []; }
    size() { return this.h.length; }
    top() { return this.h[0]; }
    push(v) { this.h.push(v); this.up(this.h.length - 1); }
    pop() {
        const top = this.h[0];
        const last = this.h.pop();
        if (this.h.length) { this.h[0] = last; this.down(0); }
        return top;
    }
    up(i) {
        while (i > 0) {
            const p = (i - 1) >> 1;
            if (this.h[p] >= this.h[i]) break;
            [this.h[p], this.h[i]] = [this.h[i], this.h[p]];
            i = p;
        }
    }
    down(i) {
        const n = this.h.length;
        while (true) {
            const l = 2 * i + 1, r = l + 1;
            let s = i;
            if (l < n && this.h[l] > this.h[s]) s = l;
            if (r < n && this.h[r] > this.h[s]) s = r;
            if (s === i) break;
            [this.h[s], this.h[i]] = [this.h[i], this.h[s]];
            i = s;
        }
    }
}

function mincostToHireWorkers(quality, wage, k) {
    const n = quality.length;
    const w = [];
    for (let i = 0; i < n; i++) w.push([wage[i] / quality[i], quality[i]]);
    w.sort((a, b) => a[0] - b[0]);
    const pq = new MaxHeap();
    let sumQ = 0;
    let best = Infinity;
    for (const [r, q] of w) {
        sumQ += q;
        pq.push(q);
        if (pq.size() > k) sumQ -= pq.pop();
        if (pq.size() === k) best = Math.min(best, sumQ * r);
    }
    return best;
}

class Solution {
    public double mincostToHireWorkers(int[] quality, int[] wage, int k) {
        int n = quality.length;
        double[][] w = new double[n][2];
        for (int i = 0; i < n; i++) {
            w[i][0] = (double) wage[i] / quality[i];
            w[i][1] = quality[i];
        }
        Arrays.sort(w, (a, b) -> Double.compare(a[0], b[0]));
        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);
        int sumQ = 0;
        double best = Double.MAX_VALUE;
        for (double[] p : w) {
            int q = (int) p[1];
            sumQ += q;
            pq.offer(q);
            if (pq.size() > k) sumQ -= pq.poll();
            if (pq.size() == k) best = Math.min(best, sumQ * p[0]);
        }
        return best;
    }
}

class MaxHeap {
    private h: number[] = [];
    size(): number { return this.h.length; }
    top(): number { return this.h[0]; }
    push(v: number): void { this.h.push(v); this.up(this.h.length - 1); }
    pop(): number {
        const top = this.h[0];
        const last = this.h.pop()!;
        if (this.h.length) { this.h[0] = last; this.down(0); }
        return top;
    }
    private up(i: number): void {
        while (i > 0) {
            const p = (i - 1) >> 1;
            if (this.h[p] >= this.h[i]) break;
            [this.h[p], this.h[i]] = [this.h[i], this.h[p]];
            i = p;
        }
    }
    private down(i: number): void {
        const n = this.h.length;
        while (true) {
            const l = 2 * i + 1, r = l + 1;
            let s = i;
            if (l < n && this.h[l] > this.h[s]) s = l;
            if (r < n && this.h[r] > this.h[s]) s = r;
            if (s === i) break;
            [this.h[s], this.h[i]] = [this.h[i], this.h[s]];
            i = s;
        }
    }
}

function mincostToHireWorkers(quality: number[], wage: number[], k: number): number {
    const n = quality.length;
    const w: [number, number][] = [];
    for (let i = 0; i < n; i++) w.push([wage[i] / quality[i], quality[i]]);
    w.sort((a, b) => a[0] - b[0]);
    const pq = new MaxHeap();
    let sumQ = 0;
    let best = Infinity;
    for (const [r, q] of w) {
        sumQ += q;
        pq.push(q);
        if (pq.size() > k) sumQ -= pq.pop();
        if (pq.size() === k) best = Math.min(best, sumQ * r);
    }
    return best;
}