Definition
- Two heaps – a min-heap orders projects by capital requirement (cheapest first), and a max-heap orders affordable projects by profit (most profitable first).
- Unlock step – each round, drain from the min-heap every project whose requirement is at most the current capital and push it into the max-heap.
- Greedy pick – take the top of the max-heap (most profitable affordable project) and add its profit to the current capital.
- K rounds – repeat the unlock-and-pick cycle at most K times, stopping early if no affordable project remains.
- Correctness – capital only grows, so a project that becomes affordable stays affordable; taking the max profit each round maximises the final capital.
At the National Bank of India, the investment desk has a budget and a list of deals. Each deal requires a minimum capital to enter and returns a profit. The desk can close at most K deals. Each closed deal increases the budget, letting them afford bigger deals next round. Each round they unlock all newly affordable deals and greedily pick the most profitable one.
Understanding the Concepts
What is the Maximize Capital problem?
The problem gives an initial capital W, a list of projects each with a capital requirement and a profit, and a limit K on the number of projects. Completing a project adds its profit to the capital. The task is to choose at most K projects to maximise the final capital.
package com.bank.service;
import java.math.BigDecimal;
import java.util.*;
public class MaximizeCapital {
public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
int n = profits.length;
// min-heap by capital requirement
PriorityQueue<int[]> minCap = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
// max-heap by profit
PriorityQueue<int[]> maxProfit = new PriorityQueue<>((a, b) -> b[1] - a[1]);
for (int i = 0; i < n; i++) minCap.offer(new int[]{capital[i], profits[i]});
for (int round = 0; round < k; round++) {
while (!minCap.isEmpty() && minCap.peek()[0] <= w) {
maxProfit.offer(minCap.poll());
}
if (maxProfit.isEmpty()) break; // no affordable project
w += maxProfit.poll()[1];
}
return w;
}
public static void main(String[] args) {
int[] profits = {1, 2, 3};
int[] capital = {0, 1, 1};
System.out.println("Max capital: "
+ new MaximizeCapital().findMaximizedCapital(2, 0, profits, capital));
}
}
Max capital: 4
Why does greedy give the optimal answer?
Capital only grows because profits are non-negative. Once a project becomes affordable, it stays affordable in all future rounds. Therefore, deferring a project never makes it unavailable. Taking the maximum profit each round grows the capital as fast as possible, which unlocks the most expensive projects soonest. This is the classic "stays ahead" argument for greedy correctness.
package com.bank.service;
public class GreedyCorrectnessProof {
// 1. Capital only grows (profits >= 0)
// 2. Once affordable, always affordable
// 3. Taking max profit grows capital fastest
// 4. Faster growth unlocks more projects sooner
// 5. Therefore greedy is optimal
public static void main(String[] args) {
System.out.println("Greedy is correct because capital only grows.");
System.out.println("Taking max profit each round cannot be beaten.");
}
}
How do the two heaps cooperate?
The min-heap gates by affordability: it surfaces the cheapest projects first. The max-heap ranks by profitability: it gives the best return among affordable projects. Each round, the unlock step moves all newly affordable projects from the min-heap to the max-heap. Then the pick step takes the most profitable one. The min-heap empties over time as capital grows and more projects become affordable.
package com.bank.service;
import java.util.*;
public class TwoHeapTrace {
public static void main(String[] args) {
int[] profits = {1, 2, 3};
int[] capital = {0, 1, 1};
int w = 0;
PriorityQueue<int[]> minCap = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
PriorityQueue<int[]> maxProfit = new PriorityQueue<>((a, b) -> b[1] - a[1]);
for (int i = 0; i < 3; i++) minCap.offer(new int[]{capital[i], profits[i]});
// Round 1: w=0, unlock projects with cap <= 0
while (!minCap.isEmpty() && minCap.peek()[0] <= w) maxProfit.offer(minCap.poll());
System.out.println("Round 1 affordable: " + maxProfit.size());
w += maxProfit.poll()[1];
System.out.println("After round 1: w=" + w);
// Round 2: w=1, unlock projects with cap <= 1
while (!minCap.isEmpty() && minCap.peek()[0] <= w) maxProfit.offer(minCap.poll());
System.out.println("Round 2 affordable: " + maxProfit.size());
w += maxProfit.poll()[1];
System.out.println("After round 2: w=" + w);
}
}
Round 1 affordable: 1
After round 1: w=1
Round 2 affordable: 2
After round 2: w=4
How do you handle money with BigDecimal?
In a real banking application, capital and profits are money and should use BigDecimal. The comparators use compareTo instead of subtraction, and the capital accumulation uses BigDecimal.add.
package com.bank.service;
import java.math.BigDecimal;
import java.util.*;
public class MaximizeCapitalBigDecimal {
record Deal(BigDecimal required, BigDecimal profit) {}
public BigDecimal maximize(int k, BigDecimal w, List<Deal> deals) {
PriorityQueue<Deal> minCap = new PriorityQueue<>(
Comparator.comparing(Deal::required));
PriorityQueue<Deal> maxProfit = new PriorityQueue<>(
Comparator.comparing(Deal::profit).reversed());
minCap.addAll(deals);
for (int round = 0; round < k; round++) {
while (!minCap.isEmpty()
&& minCap.peek().required().compareTo(w) <= 0) {
maxProfit.offer(minCap.poll());
}
if (maxProfit.isEmpty()) break;
w = w.add(maxProfit.poll().profit());
}
return w;
}
public static void main(String[] args) {
List<Deal> deals = List.of(
new Deal(new BigDecimal("0"), new BigDecimal("10000")),
new Deal(new BigDecimal("5000"), new BigDecimal("25000")),
new Deal(new BigDecimal("10000"), new BigDecimal("50000"))
);
BigDecimal result = new MaximizeCapitalBigDecimal()
.maximize(2, BigDecimal.ZERO, deals);
System.out.println("Final capital: " + result);
}
}
Final capital: 35000
How is this different from a knapsack problem?
| Feature | Maximize Capital | 0/1 Knapsack |
|---|---|---|
| Selection | sequential with growing budget | all items available at once |
| Budget grows | yes, profits add to capital | no, weight is consumed |
| Greedy works | yes (capital only grows) | no (greedy fails for knapsack) |
| Complexity | O(n log n + k log n) | O(n * W) pseudo-polynomial |
package com.bank.service;
public class CapitalVsKnapsack {
public static void main(String[] args) {
System.out.println("Capital: budget grows, greedy works.");
System.out.println("Knapsack: budget consumed, need DP.");
}
}
What are the edge cases?
Edge cases include no affordable projects (return initial capital), K larger than the number of projects (complete all affordable ones), all projects requiring more capital than available, and projects with zero profit.
package com.bank.service;
public class CapitalEdgeCases {
public static void main(String[] args) {
MaximizeCapital solver = new MaximizeCapital();
// No affordable projects
System.out.println("No affordable: "
+ solver.findMaximizedCapital(3, 0, new int[]{5}, new int[]{10}));
// K > projects
System.out.println("K > n: "
+ solver.findMaximizedCapital(10, 0, new int[]{1,2}, new int[]{0,0}));
}
}
No affordable: 0
K > n: 3
What are common mistakes?
The most common mistake is forgetting to stop early when the max-heap is empty, which would cause a NoSuchElementException. Another mistake is not draining all affordable projects from the min-heap each round, missing projects that became affordable due to increased capital.
Wrong code:
// WRONG: only moves one project per round instead of all affordable
if (!minCap.isEmpty() && minCap.peek()[0] <= w) maxProfit.offer(minCap.poll());
Correct code:
// CORRECT: drains all affordable projects
while (!minCap.isEmpty() && minCap.peek()[0] <= w) maxProfit.offer(minCap.poll());
What should a senior engineer know?
A senior engineer knows the time complexity is O(n log n) for building the min-heap plus O(k log n) for the K rounds of unlock-and-pick. They also know the greedy correctness relies on capital only growing (non-negative profits). If profits could be negative, greedy would not work and the problem would become a variant of knapsack with DP. In production at National Bank of India, the investment desk uses this logic with BigDecimal and real deal data from the database.
package com.bank.service;
public class SeniorCapitalNotes {
public static void main(String[] args) {
System.out.println("Time: O(n log n + k log n).");
System.out.println("Greedy works because capital only grows.");
System.out.println("If profits can be negative, need DP instead.");
System.out.println("Use BigDecimal for real money.");
}
}
Visual Overview
Maximize Capital: Two-Heap Greedy
Projects: cap=[0,1,1], profit=[1,2,3], W=0, K=2
Min-Heap (by cap): Max-Heap (by profit):
┌─────────────────┐ ┌──────────────┐
│ (cap=0, prof=1) │ │ (empty) │
│ (cap=1, prof=2) │ │ │
│ (cap=1, prof=3) │ │ │
└─────────────────┘ └──────────────┘
Round 1 (W=0):
Unlock: cap <= 0 => move (0,1) to max-heap
Max-Heap: [(0,1)]
Pick: profit=1, W = 0+1 = 1
Round 2 (W=1):
Unlock: cap <= 1 => move (1,2) and (1,3) to max-heap
Max-Heap: [(1,3), (1,2)]
Pick: profit=3, W = 1+3 = 4
Result: W = 4
Key Takeaway
Maximize Capital is a two-heap greedy problem where a min-heap gates projects by affordability and a max-heap ranks them by profitability. Each round, all newly affordable projects are moved from the min-heap to the max-heap, and the most profitable one is picked. Its profit increases the capital, which unlocks more projects next round.
The greedy choice is correct because capital only grows. Once a project becomes affordable, it stays affordable. Taking the maximum profit each round grows the capital as fast as possible, which cannot be beaten. If profits could be negative, this argument breaks and the problem becomes a DP variant.
The time complexity is O(n log n) for heap setup plus O(k log n) for the K rounds. Each round drains all affordable projects from the min-heap and picks one from the max-heap. The algorithm stops early if no affordable project remains.
At National Bank of India, the investment desk uses this logic with BigDecimal capital and profit values from the deal database. Each closed deal enlarges the budget for the next, and the desk greedily closes the most profitable affordable deal each round to maximise the final portfolio value.
Remember one sentence: use a min-heap to unlock affordable projects and a max-heap to greedily pick the most profitable one each round, because capital only grows.
---