LeetCode 502. IPO

2024.6.15 Daily Challenge

難度：Hard

問題

參數

k 可以做幾個 project

w 現在有多少 capital

profits, capital project 所需 capital 的 array

說明

你可以做 k 個 project，每個 project 最多只能做一次。

只有在滿足 current_capital > capital[i] 才能做 project i 。

做完一個 project 你的 capital 可以增加 profit[i]。

請解出 max profit。

解法

一直很不想面對，隔天才寫出來。本來以為做完 project 會消耗 capital，但其實不會。

結論是維護一個 projectProfits 的 PriorityQueue，在 current_capital 增加時把 capital[i] < current_capital 的 project profit 都加進去，每次選最大的做就行。

import java.util.PriorityQueue

data class Project(
	val capital: Int,
	val profit: Int
)

class Solution502 {
	fun findMaximizedCapital(k: Int, w: Int, profits: IntArray, capital: IntArray): Int {
		val allProjects = PriorityQueue<Project>(compareBy { it.capital })
		profits.indices.forEach {
			allProjects.add(
				Project(capital[it], profits[it])
			)
		}

		val projectProfits = PriorityQueue<Int>(compareBy { -it })
		var ans = w

		for (i in 0 until k) {
			while (allProjects.isNotEmpty() && allProjects.peek().capital <= ans) {
				projectProfits.add(allProjects.poll().profit)
			}

			if (projectProfits.isEmpty()) {
				break
			}

			ans += projectProfits.poll()
		}

		return ans
    }
}