題目描述:有 n 個項目,每個項目有利潤 profits[i] 和最低啟動資金 capital[i]。初始資金為 w,最多可完成 k 個項目(每次完成後資金增加對應利潤),求最大化最終資金。
解題思路:貪心策略:每次從「目前資金可負擔」的項目中選擇利潤最高的。用最小堆按啟動資金排序所有項目,每輪將所有可負擔項目推入最大堆(按利潤);從最大堆彈出利潤最高者執行,重複 k 次。
時間複雜度:O(n log n + k log n) — 建堆 O(n log n);k 輪每輪最多 O(log n) 操作。
空間複雜度:O(n) — 兩個堆共儲存 n 個項目。
1. Push all (capital[i], profits[i]) into min-heap by capital
2. Repeat k times:
a. While min-heap not empty AND min-heap.top().capital <= w:
- Pop from min-heap, push profit into max-heap
b. If max-heap empty: break (no affordable project)
c. w += max-heap.top(); pop from max-heap
3. Return w排序 + 線段樹 O((n + k) log n):按資金排序後,每輪用線段樹查詢可負擔範圍的最大利潤 — 實作複雜,無實質優勢。
暴力法 O(k × n):每輪線性掃描可負擔項目找最大利潤 — 正確但當 k 和 n 都大時過慢。