Dynamically building the heap

Question

IPO

Naive Solution got TLE

The time complexity is about O(k*m), where m is number of unique profits.

The basic idea is organize the data by profit and each time checking from higher profit to lower profit to harvest the highest profit project.

class Solution {
public:
    int findMaximizedCapital(int k, int w, vector<int>& profits, vector<int>& capital) {
       map<int, vector<int>> projects;
       const int n = capital.size();
       for (int i = 0; i < n; ++i){
           projects[profits[i]].push_back(capital[i]);
       }
       for (auto &[k,v]:projects){
           sort(v.begin(), v.end(), greater<int>());
       }
       int tot_capital = w;
       int num_proj = 0;
       while (true){
           bool found = false;
           int to_be_erased = -1;
           for (auto it = projects.rbegin(); it != projects.rend(); it++){
               auto s = it -> second;
               if (s.back() > tot_capital){
                   continue;
               } else {
                   tot_capital += it -> first;
                   found = true;
                   num_proj ++;
                   if (num_proj == k)return tot_capital;
                   it->second.pop_back();
                   if (it -> second.empty()){
                       to_be_erased = it -> first;
                   }
                   break;
               }
           }
           if (!found) return tot_capital;
           if(to_be_erased != -1)projects.erase(to_be_erased);
       }
    return 0;
    }
};

A better way

Actually, when solving those problems, a usual way that we can think is sorting the data. After sorting by capital, with the gaining of benefit, we can add previously not qualified projects to a priority queue, so we can:

1. Increase the overall elements of the priority queue by adding more qualified projects.
2. We can easily find the highest profit one by using a max heap.
3. We will not miss any element .

A more clean explanation can be found in [1]

struct Project{
    public:
    int profit;
    int capital;
    Project(int profit, int capital):profit(profit), capital(capital){
    }
};

class Solution {
public:
    int findMaximizedCapital(int k, int w, vector<int>& profits, vector<int>& capital) {
       vector<Project> projects;
       const int n = profits.size();
       for (int i = 0; i < n; ++i){
           projects.push_back(Project(profits[i], capital[i]));
       }
       sort(projects.begin(), projects.end(), [](const auto & lhs, const auto & rhs ){return lhs.capital < rhs.capital;});
       int tot_capital = w;
       priority_queue<int> qualified_project_profits;
       int i = 0;
       while (k--){
           while (i < n && projects[i].capital <= tot_capital){
               qualified_project_profits.push(projects[i].profit);
               i++;
           }
           if (qualified_project_profits.empty())break;
           tot_capital += qualified_project_profits.top();qualified_project_profits.pop();
       }
    return tot_capital;
    }
};

Reference

[1] https://leetcode.com/problems/ipo/solutions/3219987/day-54-c-priority-queue-easiest-beginner-friendly-sol/?orderBy=most_votes