Two pools (available / locked) (Two Heaps Sub-pattern)
One heap holds what can be used now, ordered by quality; the other holds what unlocks later, ordered by unlock time or cost. Move items across as the condition changes.
- ›
"assign each task to the free server with the smallest weight"
- ›
"pick the cheapest worker from the first or last c candidates"
- ›
"choose at most k projects you can afford to maximise capital"
Process Tasks Using Servers: free by (weight, index), busy by (free time, …). When nothing is free, jump time to the next finish. Total Cost to Hire K Workers isn't "now vs later" but "front vs back": two min-heaps fed by two pointers that must never overlap, ties to the front. IPO: sort projects by capital and push every newly affordable profit into a max-heap; capital only grows, so taking the biggest affordable profit is always safe.
Questions
ordered from “learn the idea” to “recognise it without help”- 1Process Tasks Using ServersWalkthroughMediumBasic Anchor·LeetCode #1882
- 2Total Cost to Hire K WorkersWalkthroughMediumMedium·LeetCode #2462
- 3IPOWalkthroughHardInterview-Level·LeetCode #502
Template
// IPO: locked projects sorted by capital; available profits in a max-heap.
int findMaximizedCapital(int k, int w, vector<int>& profits, vector<int>& capital) {
int n = profits.size();
vector<pair<int, int>> locked; // (capital needed, profit)
for (int i = 0; i < n; i++) locked.push_back({capital[i], profits[i]});
sort(locked.begin(), locked.end()); // unlock order
priority_queue<int> available; // profits we can afford now
int p = 0;
while (k--) {
while (p < n && locked[p].first <= w) // move EVERY unlocked project across
available.push(locked[p++].second);
if (available.empty()) break; // nothing affordable: stop
w += available.top(); available.pop(); // best affordable project
}
return w;
}