IPO (Maximize Capital)

class Solution {
public:
    int findMaximizedCapital(int k, int w, vector<int>& profits, vector<int>& capital) {
        int n = profits.size();
        vector<pair<int,int>> p(n);
        for (int i = 0; i < n; ++i) p[i] = {capital[i], profits[i]};
        sort(p.begin(), p.end());
        priority_queue<int> pq;
        int i = 0;
        while (k--) {
            while (i < n && p[i].first <= w) pq.push(p[i++].second);
            if (pq.empty()) break;
            w += pq.top(); pq.pop();
        }
        return w;
    }
};

import (
    "container/heap"
    "sort"
)

type maxHeap []int

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

func findMaximizedCapital(k int, w int, profits []int, capital []int) int {
    n := len(profits)
    idx := make([]int, n)
    for i := range idx {
        idx[i] = i
    }
    sort.Slice(idx, func(a, b int) bool { return capital[idx[a]] < capital[idx[b]] })
    pq := &maxHeap{}
    i := 0
    for ; k > 0; k-- {
        for i < n && capital[idx[i]] <= w {
            heap.Push(pq, profits[idx[i]])
            i++
        }
        if pq.Len() == 0 {
            break
        }
        w += heap.Pop(pq).(int)
    }
    return w
}

from typing import List
import heapq

class Solution:
    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:
        n = len(profits)
        projects = sorted(zip(capital, profits))
        pq: List[int] = []
        i = 0
        for _ in range(k):
            while i < n and projects[i][0] <= w:
                heapq.heappush(pq, -projects[i][1])
                i += 1
            if not pq:
                break
            w += -heapq.heappop(pq)
        return w

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

function findMaximizedCapital(k, w, profits, capital) {
    const n = profits.length;
    const p = Array.from({ length: n }, (_, i) => [capital[i], profits[i]]);
    p.sort((a, b) => a[0] - b[0]);
    const pq = new MaxHeap();
    let i = 0;
    while (k--) {
        while (i < n && p[i][0] <= w) pq.push(p[i++][1]);
        if (pq.size() === 0) break;
        w += pq.pop();
    }
    return w;
}

class Solution {
    public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
        int n = profits.length;
        int[][] p = new int[n][2];
        for (int i = 0; i < n; i++) {
            p[i][0] = capital[i];
            p[i][1] = profits[i];
        }
        Arrays.sort(p, (a, b) -> a[0] - b[0]);
        PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.reverseOrder());
        int i = 0;
        while (k-- > 0) {
            while (i < n && p[i][0] <= w) pq.offer(p[i++][1]);
            if (pq.isEmpty()) break;
            w += pq.poll();
        }
        return w;
    }
}

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

function findMaximizedCapital(k: number, w: number, profits: number[], capital: number[]): number {
    const n = profits.length;
    const p: [number, number][] = Array.from({ length: n }, (_, i) => [capital[i], profits[i]]);
    p.sort((a, b) => a[0] - b[0]);
    const pq = new MaxHeap();
    let i = 0;
    while (k--) {
        while (i < n && p[i][0] <= w) pq.push(p[i++][1]);
        if (pq.size() === 0) break;
        w += pq.pop();
    }
    return w;
}