Interview Classic 150 Questions P502 IPO

---

Timeline

Timeline

2025-12-08

init

Heap sort

---

Problem:

P502 IPO

https://leetcode.cn/problems/ipo/?envType=study-plan-v2&envId=top-interview-150

Heap sort: each time, put all profits less than or equal to current capital into the heap, take the maximum, then update capital, and repeat until k times or no projects are available.

#include <vector>
#include <unordered_map>
#include <utility>
#include <algorithm>
#include <queue>

using std::vector;
using std::unordered_map;
using std::pair;
using std::priority_queue;

class Solution {
    public:
        int findMaximizedCapital(int k, int w, vector<int> &profits,
                                 vector<int> &capital)
        {
                int n = profits.size();
                int i, selected = 0;

                vector<pair<int, int> > prof2cap;

                for (i = 0; i < n; i++) {
                        prof2cap.push_back({ profits[i], capital[i] });
                }

                std::sort(prof2cap.begin(), prof2cap.end(),
                          [](pair<int, int> &l, pair<int, int> &r) {
                                  return l.second < r.second;
                          });
                priority_queue<int> profit_heap;

                i = 0;
                while (k--) {
                        // Add all projects with capital less than w to the heap.
                        while (i < n && prof2cap[i].second <= w) {
                                profit_heap.push(prof2cap[i++].first);
                        }

                        if (profit_heap.empty()) {
                                break;
                        }

                        w += profit_heap.top();
                        profit_heap.pop();
                }
                return w;
        }
};