# 15.06.2024 [502. IPO]

Max capital by choosing `k` jobs with `profits[] & capital[]` given `w` on start #hard #heap

15.06.2024

502. IPO hard
blog post

youtube

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/640

Problem TLDR

Max capital by choosing k jobs with profits[] & capital[] given w on start #hard #heap

Intuition

Let’s observe how this works:

    // profits        capital
    // 2 3 4 5 6      1 2 0 3 3      w = 0   k = 3
    // 1 1 4 2 3
    // `cap` only increases

We can choose from a bucket of jobs; each must have capital <= current money. After each job is done our money will only grow, and the bucket will expand. And to choose optimally, just take max capital job.

The growing sorted bucket can be done with heap. It is evident that bucket must take new job with the smaller capital first, so sort by capital initially.

Approach

• note that heap in Kotlin is a min-heap; in Rust is a max-heap

Complexity

• Time complexity:
  𝑂(𝑛𝑙𝑜𝑔(𝑛))

• Space complexity:
  𝑂(𝑛)

Code

    fun findMaximizedCapital(k: Int, w: Int, profits: IntArray, capital: IntArray): Int {
        val inds = profits.indices.sortedBy { capital[it] }; val pq = PriorityQueue<Int>()
        var cap = w; var j = 0
        repeat (k) {
            while (j < inds.size && capital[inds[j]] <= cap) pq += -profits[inds[j++]]
            cap -= pq.poll() ?: 0
        }
        return cap
    }

    pub fn find_maximized_capital(k: i32, w: i32, profits: Vec<i32>, capital: Vec<i32>) -> i32 {
        let mut inds: Vec<_> = (0..profits.len()).collect(); inds.sort_by_key(|&i| capital[i]);
        let (mut cap, mut bh, mut j) = (w, BinaryHeap::new(), 0);
        for _ in 0..k {
            while j < inds.len() && capital[inds[j]] <= cap { bh.push(profits[inds[j]]); j += 1 }
            cap += bh.pop().unwrap_or(0)
        }; cap
    }