502. IPO

Description

image-20210908203015388

image-20210908203024856

Solution

Fix capital then find maximal profit by priority_queue

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    static bool cmp(pair<int,int>a, pair<int,int>b){
        return a.second < b.second;
    }
public:
    int findMaximizedCapital(int k, int w, vector<int>& profits, vector<int>& capital) {
        //find the maximal profit under current capital
        priority_queue<int, vector<int>, less<>> pq;
        vector<pair<int,int>> projs;
        for(int i = 0; i < profits.size(); i++)
            projs.push_back({profits[i], capital[i]});
        sort(projs.begin(), projs.end(), cmp);
        int start = 0, i;
        while(k--){
            for(i = start; i < projs.size() && projs[i].second <= w; i++)
                pq.push(projs[i].first);
            start = i;
            if(pq.empty()){
                return w;
            }
            w += pq.top();
            pq.pop();
        }
        return w;
    }
};