C++ solution using multimap


  • 0
    V

    Similar to 77768, a simple greedy algorithm that gets the next smallest capital and tries to add it to profit.

    This simply works because we look at all possible allowed capitals, but will only pick the one with the highest profit.
    Note that the complexity here is O(NlgN), but this solution although simple, will be slower than a priority_queue solution (which is of the same complexity), simply because priority_queue is implemented using a vector internally.

    class Solution {
    public:
        int findMaximizedCapital(int k, int W, vector<int>& Profits, vector<int>& Capital) {
            multimap<int, int> capitals;
            for (int i = 0, e = Profits.size(); i < e; i++ ){
                capitals.insert(std::pair<int, int>(Capital[i], Profits[i]));
            }
            
            multimap<int, int, std::greater<int>> profits;
            for (int i = 0; i < k; i++) {
                auto lower = capitals.upper_bound(W);
                for (auto itr = capitals.begin(); itr != capitals.end() && itr != lower;) {
                    profits.insert(std::pair<int, int>(itr->second, itr->first));
                    itr = capitals.erase(itr);
                }
                if (profits.empty()) {
                    break;
                }
                auto max = profits.begin();
                W += (*max).first;
                profits.erase(max);
            }
            
            return W;
        }
    };
    ```

Log in to reply
 

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