LeetCode Entry
502. IPO
Max capital by choosing k jobs with profits[] & capital[] given w on start
502. IPO hard
blog post
substack
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 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 the bucket must take a new job with the smalled 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: \(O(nlog(n))\)
-
Space complexity: \(O(n)\)
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
}