C++ 72ms with multimap and nth_element


  • 0
    H
    class Solution {
    public:
        int findMaximizedCapital(int k, int W, vector<int>& Profits, vector<int>& Capital) {
            multimap<int, int> m;
            for (int i = 0; i < Capital.size(); i++) {
                m.emplace(Capital[i], Profits[i]); 
            }
            int res = W;
            while (k > 0 && m.size()) {
                auto end = m.upper_bound(res);
                if (end == m.begin()) return res; // no enough capital for any project
                if (end == m.end()) { // eligible for all project, then just pick up first k
                    vector<int> v;
                    int sum = 0;
                    for (auto it = m.begin(); it != end; it++) {
                        v.push_back(it->second);
                        sum += it->second;
                    }
                    if (k >= m.size()) res += sum;
                    else {
                        nth_element(v.begin(), v.begin()+k, v.end(), greater<int>());
                        for (int i = 0; i < k; i++) res += v[i];
                    }
                    return res; // all set
                }
                // pick up the max profit in the eligible range
                auto max_p = m.begin();
                for (auto it = m.begin(); it != end; it++) {
                    if (it->second > max_p->second) max_p = it;
                }
                res += max_p->second;
                m.erase(max_p);
                k--;
            }
            return res;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.