LeetCode Entry
502. IPO
Sort items by increasing capital. Then, on each step, add all possible deals to the priority queue and take one best from it.
502. IPO hard
fun findMaximizedCapital(k: Int, w: Int, profits: IntArray, capital: IntArray): Int {
val indices = Array(profits.size) { it }.apply { sortWith(compareBy( { capital[it] })) }
var money = w
with(PriorityQueue<Int>(profits.size, compareBy({ -profits[it] }))) {
var i = 0
repeat (k) {
while (i <= indices.lastIndex && money >= capital[indices[i]]) add(indices[i++])
if (isNotEmpty()) money += profits[poll()]
}
}
return money
}
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/127
Intuition
My first (wrong) intuition: greedy add elements to the min-profit priority queue, then remove all low-profit elements from it, keeping essential items. It wasn’t working, and the solution became too verbose. Second intuition, after the hint: greedy add elements to the max-profit priority queue, then remove the maximum from it, which will be the best deal for the current money.
Approach
Sort items by increasing capital. Then, on each step, add all possible deals to the priority queue and take one best from it.
Complexity
- Time complexity: \(O(nlog_2(n))\)
- Space complexity: \(O(n)\)