假設你有初始資本
w，最多可以完成k個專案。每個專案有最低資本需求capital[i]和淨利潤profits[i]。完成專案後利潤加入總資本。選擇最多k個專案使得最終資本最大化。
Example:
Input: k = 2, w = 0, profits = [1,2,3], capital = [0,1,1] Output: 4
Intuition
TIP
核心思路：貪心地每次從「當前資本能負擔的專案」中選利潤最高的，用兩個 Heap 管理。
- 每做一個專案，資本增加，能解鎖更多專案
- 貪心策略：每次從可負擔的專案中選利潤最高的
- 用 Min Heap 依 capital 排序所有專案，方便依資本門檻逐步解鎖
- 用 Max Heap 存所有已解鎖專案的利潤，每次取最大
Approaches
1. Brute Force: Scan for Best Affordable Project per Round — O(k·n) / O(n)
- Idea: 每輪線性掃過所有未做專案，從資本足夠的當中選利潤最高者
- Time:
O(k·n)- k 輪、每輪掃描 O(n) - Space:
O(n)- used 標記
class Solution {
fun findMaximizedCapital(k: Int, w: Int, profits: IntArray, capital: IntArray): Int {
val n = profits.size
val used = BooleanArray(n)
var cur = w
repeat(k) {
var best = -1
for (i in 0 until n) {
if (!used[i] && capital[i] <= cur && (best == -1 || profits[i] > profits[best])) best = i
}
if (best == -1) return cur // 沒有可負擔的專案
used[best] = true
cur += profits[best]
}
return cur
}
}⭐ 2. Two Heaps (Min + Max) — O(n log n) / O(n)
- Idea: Min Heap 依資本需求排序專案，每輪將可負擔的專案利潤推入 Max Heap，取最大利潤執行
- Time:
O(n log n)- 排序 + heap 操作 - Space:
O(n)
class Solution {
fun findMaximizedCapital(k: Int, w: Int, profits: IntArray, capital: IntArray): Int {
val n = profits.size
val indices = (0 until n).sortedBy { capital[it] }
val maxHeap = PriorityQueue<Int>(compareByDescending { it })
var currentCapital = w
var i = 0
repeat(k) {
// 解鎖所有當前資本能負擔的專案
while (i < n && capital[indices[i]] <= currentCapital) {
maxHeap.offer(profits[indices[i]])
i++
}
// 選利潤最高的專案
if (maxHeap.isEmpty()) return currentCapital
currentCapital += maxHeap.poll()
}
return currentCapital
}
}🔑 Takeaways
- Pattern: 「資源逐步解鎖」→ Min Heap 管理未解鎖的，Max Heap 管理已解鎖的
- Key trick: 依資本排序後用指標逐步解鎖，避免每輪重新掃描；此雙 Heap 模式常見於貪心 + 排程類問題