Description Link to heading

502.IPO

Solution Link to heading

Greedy algorithm: if we want to maximize the final capital, we choose the project whose profit is maximum and whose minimum captial required is less than or equal to our current capital.

map<int, map<int, int>, std::greater<int>> projs

Let key be the profits, value be a map, of which key is the minimum capital required while value is the amount of the corresponding project.

Code Link to heading 

class Solution {
public:
    int findMaximizedCapital(int k, int w, vector<int>& profits, vector<int>& capital) {
        map<int, map<int, int>, std::greater<int>> projs;
        for (int i = 0; i < profits.size(); i++) {
            projs[profits[i]][capital[i]]++;
        }
        for (int i = 0; i < k; i++) {
            int find_flag = 0;
            for (auto &prj : projs) {
                if (w >= ((prj.second).begin())->first) {
                    w += prj.first;
                    prj.second.begin()->second--; // 该项目已经完成
                    if (prj.second.begin()->second == 0)
                        prj.second.erase(prj.second.begin());
                    if (prj.second.empty())
                        projs.erase(prj.first);
                    find_flag = 1;
                    break;
                }
            }
            if (find_flag == 0) // 如果任何项目的最小资本需求都不能满足，就要结束IPO
                return w;
        }
        return w;
    }
};