502. IPO

Hard

Description

假設你有初始資本 w，最多可以完成 k 個專案。每個專案有最低資本需求 capital[i] 和淨利潤 profits[i]。完成專案後利潤加入總資本。選擇最多 k 個專案使得最終資本最大化。

Example:

Input: k = 2, w = 0, profits = [1,2,3], capital = [0,1,1] Output: 4

Intuition#

核心思路：貪心地每次從「當前資本能負擔的專案」中選利潤最高的，用兩個 Heap 管理。

每做一個專案，資本增加，能解鎖更多專案
貪心策略：每次從可負擔的專案中選利潤最高的
用 Min Heap 依 capital 排序所有專案，方便依資本門檻逐步解鎖
用 Max Heap 存所有已解鎖專案的利潤，每次取最大

Approaches#

⭐1: 雙 Heap（Min Heap + Max Heap）#

概念: Min Heap 依資本需求排序專案，每輪將可負擔的專案利潤推入 Max Heap，取最大利潤執行
時間複雜度: O(n log n) - 排序 + heap 操作
空間複雜度: 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 管理已解鎖的
關鍵技巧: 依資本排序後用指標逐步解鎖，避免每輪重新掃描；此雙 Heap 模式常見於貪心 + 排程類問題