IPO: เพิ่มทุนสูงสุดก่อน IPO ใน C++

ปัญหา

บริษัทต้องการทำ IPO มีโครงการหลายโครงการ แต่ละโครงการมี profit และ capital ต่ำสุดที่ต้องใช้ เริ่มต้นมีทุน W ทำโครงการได้สูงสุด k โครงการ หาทุนสูงสุดสุดท้าย

ตัวอย่าง: k=2, W=0, profits=[1,2,4], capitals=[0,1,1] → ทำโครงการ 0 (ได้ 1) → ทุน=1 → ทำโครงการ 2 (ได้ 4) → รวม = 5

แนวคิด: Two Priority Queues (Greedy)

Data Structures

• pqCapital: Min-Heap เรียงตาม capital (โครงการที่ยังทำไม่ได้)
• pqProfit: Max-Heap เรียงตาม profit (โครงการที่ทำได้แล้ว)

Algorithm

1. Push ทุกโครงการเข้า pqCapital
2. ทำซ้ำ k รอบ:
   • ย้ายโครงการจาก pqCapital → pqProfit ทุกตัวที่ capital ≤ W
   • ถ้า pqProfit ว่าง → หยุด
   • Pop โครงการ profit สูงสุดจาก pqProfit เพิ่มเข้า W
3. คืน W

โค้ด C++

#include <bits/stdc++.h>
using namespace std;

struct CapitalComparator {
    bool operator()(pair<int, int> a, pair<int, int> b) {
        return a.second > b.second;  // Min-heap by capital
    }
};

class Solution {
public:
    int findMaximizedCapital(int k, int W, vector<int>& profits, vector<int>& capitals) {
        priority_queue<pair<int, int>, vector<pair<int, int>>, CapitalComparator> pqCapital;
        priority_queue<int> pqProfit;  // Max-heap by profit
        
        int n = profits.size();
        for (int i = 0; i < n; i++) {
            pqCapital.push({profits[i], capitals[i]});
        }
        
        for (int i = 0; i < k; i++) {
            // ย้ายโครงการที่ทำได้เข้า pqProfit
            while (!pqCapital.empty() && pqCapital.top().second <= W) {
                pqProfit.push(pqCapital.top().first);
                pqCapital.pop();
            }
            
            if (pqProfit.empty()) break;  // ไม่มีโครงการทำได้แล้ว
            
            W += pqProfit.top();
            pqProfit.pop();
        }
        
        return W;
    }
};

int main() {
    Solution ob;
    vector<int> profits = {1, 2, 4};
    vector<int> capitals = {0, 1, 1};
    cout << ob.findMaximizedCapital(2, 0, profits, capitals);  // 5
    return 0;
}

การทำงานตัวอย่าง

ความซับซ้อน

• Time: O(n log n + k log n)
• Space: O(n)

Input / Output

Input:  k=2, W=0, profits=[1,2,4], capitals=[0,1,1]
Output: 5