Problem link ও উৎস
- **Original source:** Classic capital-bounded greedy with two heaps
- **Platform:** LeetCode —
- **Topic:** heap / priority queue
- **Difficulty:** Hard
- **Pattern:** Two heaps + greedy (affordable min-heap by capital → max-heap by profit)
- **Basic idea inherited from:** `08` two heaps + greedy — unlock-by-threshold, তারপর সবচেয়ে লাভজনকটা নাও
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
তোমার হাতে শুরুতে `w` পরিমাণ capital আছে, আর কতগুলো project আছে। প্রতিটা project-এর দুটো সংখ্যা: শুরু করতে যত capital লাগবে (`capital[i]`), আর শেষ হলে যত profit যোগ হবে (`profits[i]`)। তুমি বড়জোর `k`-টা project করতে পারবে, একটার পর একটা। কোনো project শুরু করতে হলে এই মুহূর্তে তোমার capital তার `capital[i]`-এর সমান বা বেশি হতে হবে; শেষ হলে profit তোমার capital-এ যোগ হয়। `k`-টা project শেষে সর্বোচ্চ কত capital হতে পারে, সেটা return করো।
```text
w = 0, k = 2, profits = [1, 2, 3], capital = [0, 1, 1] -> 4
```
### Input ও output {#8-example-input-and-output}
```text
Input : w=0, k=2, profits=[1,2,3], capital=[0,1,1] -> Output: 4
Input : w=0, k=3, profits=[1,2,3], capital=[0,1,2] -> Output: 6 (তিনটেই করা যায়)
Input : w=2, k=1, profits=[5], capital=[5] -> Output: 2 (afford হয় না)
Input : w=0, k=0, profits=[1,2], capital=[0,0] -> Output: 0 (k=0, কিছুই না)
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো তুমি একজন investor। সামনে অনেক startup, প্রত্যেকের একটা "ঢোকার টিকিট দাম" (capital) আর একটা প্রত্যাশিত "return" (profit)। যেগুলোর টিকিট তোমার এখনকার টাকায় কেনা যায়, সেগুলো একটা টেবিলে রাখো — আর সেই টেবিল থেকে সবসময় সবচেয়ে বেশি return-এর টা আগে বেছে নাও। একটা ভালো deal শেষ হলে পকেট ভারী হয়, তখন আরও দামি টিকিটও নাগালে আসে। "সস্তা গুলো খোলো, লাভজনকটা নাও" — সেই দুই টেবিলই দুই heap।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
ভিত `08`-এর **two heaps + greedy**। একটা min-heap সব project-কে **capital** অনুযায়ী সাজিয়ে রাখে — যাতে "এখনকার টাকায় কোনগুলো affordable" সেটা সস্তায় বের করা যায়। আরেকটা max-heap সেই affordable project-গুলোর **profit** ধরে রাখে — যাতে তাদের মধ্যে সবচেয়ে লাভজনকটা চট করে নেওয়া যায়। এটা ঠিক `001`-এর negate-for-max trick আর greedy "locally-best choice"-এরই বড় ভাই।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic একটা **greedy exchange argument**: প্রতি round-এ এই মুহূর্তে যেটা afford করতে পারো তাদের মধ্যে সবচেয়ে বেশি profit-দেওয়া project নেওয়া কখনো ভুল না। কারণ profit শুধু capital বাড়ায়, কমায় না — তাই বেশি profit আগে নিলে পরের round-এ affordable project-এর set কেবল বড় হয় (বা সমান থাকে), কখনো ছোট হয় না। তাই প্রতি step-এ সবচেয়ে লাভজনকটা নিলে শেষে capital maximize হয়।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
**দুটো heap।** (1) `by_capital` — সব (এখনো না-করা) project-এর **min-heap**, key = required capital। (2) `affordable` — যেগুলোর capital বর্তমান `w`-এর নিচে নেমে এসেছে তাদের profit-এর **max-heap** (heapq min-heap বলে profit negate করে রাখা)।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
প্রতি round-এ তোমার দুটো প্রশ্ন: "এই capital-এ কোন project গুলো খুলে গেল?" আর "তাদের মধ্যে সবচেয়ে লাভজনক কে?"। min-heap (capital দিয়ে sorted) প্রথমটার উত্তর দেয় — top সস্তা হলেই pop করে affordable-এ সরাও। max-heap (profit) দ্বিতীয়টার উত্তর O(log n)-এ দেয়। পুরো list বারবার scan বা re-sort করার দরকারই পড়ে না।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: প্রতি round-এ পুরো project list scan করো, এখন afford করা যায় এমন সবগুলোর মধ্যে সবচেয়ে বেশি profit-এর টা খুঁজে নাও, করো, capital update করো, project-টা mark করে বাদ দাও। `k` বার এটা চালাও।
```text
round-প্রতি: পুরো list scan -> affordable-দের মধ্যে max profit -> নাও
k round x n project = O(k * n) scan
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
প্রতি round-এ পুরো list scan মানে O(n), আর round হয় `k`-টা — মোট **O(k·n)**, যেখানে n বড় হলে এটা ভারী। অথচ আমাদের প্রতিবার সবগুলো দেখার দরকার নেই: একবার capital-sorted করে রাখলে নতুন কোন project খুলেছে সেটা incremental-ভাবে জানা যায়, আর max profit heap O(log n)-এ দেয়।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: capital শুধু **বাড়ে**। তাই কোনো project একবার affordable হলে চিরকাল affordable থাকে — কখনো আবার "দামি" হয়ে যায় না। মানে capital-sorted list-এর ওপর একটা pointer শুধু সামনে এগোয়, পিছায় না। আর affordable হয়ে যাওয়া project-গুলোর মধ্যে শুধু সবচেয়ে লাভজনকটাই দরকার — পুরো order না।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
সব project-কে capital দিয়ে একটা min-heap-এ ঢালো (বা শুধু sort করো)। `k` বার loop: বর্তমান `w`-এর `<=` capital-ওয়ালা সব project min-heap থেকে pop করে profit max-heap-এ ঢালো। max-heap খালি হলে আর কিছু afford হয় না — থামো। নাহলে সবচেয়ে বড় profit pop করে `w`-তে যোগ করো। প্রতিটা push/pop O(log n), মোট O(n log n)।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "project বাছাই" না ভেবে ভাবো "একটা unlock gate + একটা reward chest।" Capital-min-heap হলো gate — capital বাড়ার সাথে সাথে নতুন project খুলে দেয়; profit-max-heap হলো chest — খোলা জিনিসগুলোর মধ্যে সেরাটা দেয়। "একটা threshold পেরোলে নতুন option খোলে, খোলা option-দের মধ্যে best নাও" — এমন গন্ধ পেলেই এই two-heaps pattern মনে করবে।
### ছবিতে বোঝা {#7-visual-explanation}
`w = 0, k = 2, profits = [1, 2, 3], capital = [0, 1, 1]`:
```text
by_capital (min-heap, key=capital): (0,p1) (1,p2) (1,p3)
affordable (max-heap, key=profit): খালি
round 1: w=0 -> capital<=0 খোলো -> (0,p1) সরাও
affordable: [profit 1]
সবচেয়ে লাভজনক pop -> +1 -> w = 1
round 2: w=1 -> capital<=1 খোলো -> (1,p2),(1,p3) সরাও
affordable: [profit 3, profit 2]
সবচেয়ে লাভজনক pop -> +3 -> w = 4
k=2 শেষ -> উত্তর 4
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input `w=0, k=2, profits=[1,2,3], capital=[0,1,1]`:
1. by_capital min-heap: (0,1), (1,2), (1,3); affordable max-heap: খালি; w = 0
2. round 1: top capital 0 ≤ 0 → pop (0,1), affordable-এ profit 1 ঢালো; পরের top capital 1 > 0 → থামো। affordable = {1}
3. সবচেয়ে বড় profit pop → 1 → w = 0 + 1 = 1
4. round 2: top capital 1 ≤ 1 → pop (1,2) ঢালো; আবার top 1 ≤ 1 → pop (1,3) ঢালো; by_capital খালি। affordable = {3, 2}
5. সবচেয়ে বড় profit pop → 3 → w = 1 + 3 = 4
6. k = 2 শেষ → return 4
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
import heapq
def find_maximized_capital(k, w, profits, capital):
# সব project capital দিয়ে min-heap-এ: (required_capital, profit)
by_capital = list(zip(capital, profits))
heapq.heapify(by_capital)
affordable = [] # profit-এর max-heap (negate করা)
for _ in range(k):
# বর্তমান w-তে যা যা afford হয়, সব affordable-এ সরাও
while by_capital and by_capital[0][0] <= w:
cap, prof = heapq.heappop(by_capital)
heapq.heappush(affordable, -prof) # negate: max-heap
if not affordable: # কিছুই afford হয় না -> থামো
break
w += -heapq.heappop(affordable) # সবচেয়ে লাভজনকটা নাও
return w
# ---- tests ----
assert find_maximized_capital(2, 0, [1, 2, 3], [0, 1, 1]) == 4
assert find_maximized_capital(3, 0, [1, 2, 3], [0, 1, 2]) == 6 # তিনটেই
assert find_maximized_capital(1, 2, [5], [5]) == 2 # afford হয় না
assert find_maximized_capital(0, 0, [1, 2], [0, 0]) == 0 # k=0
assert find_maximized_capital(10, 0, [1, 2, 3], [0, 1, 1]) == 6 # k > project সংখ্যা
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `by_capital = list(zip(capital, profits))` — প্রতিটা project-কে `(capital, profit)` জোড়ায় বাঁধি; tuple বলে heap capital দিয়ে sort করবে।
- `heapq.heapify(by_capital)` — O(n)-এ min-heap; top সবসময় সবচেয়ে সস্তা (কম capital) project।
- `affordable = []` — যেগুলো খুলে গেছে তাদের profit-এর max-heap (negate করে রাখা)।
- `while by_capital and by_capital[0][0] <= w:` — top-এর required capital বর্তমান `w`-এর নিচে থাকলেই সেটা affordable; pop করে সরাও।
- `heapq.heappush(affordable, -prof)` — profit negate করে push; এতে min-heap max-heap-এর মতো আচরণ করে।
- `if not affordable: break` — হাতে capital দিয়ে কোনো project-ই শুরু করা যায় না → আর এগোনো অর্থহীন, থামো।
- `w += -heapq.heappop(affordable)` — সবচেয়ে বড় profit pop করে (negate ফিরিয়ে) `w`-তে যোগ।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`find_maximized_capital(2, 0, [1,2,3], [0,1,1])` section 14-এর dry run মেনে 4 দেয় — assert pass। `k=3, capital=[0,1,2]`-এ তিনটেই ধাপে ধাপে খুলে যায় → 1+2+3 = 6। `w=2, capital=[5]`-এ একমাত্র project-এর টিকিট 5, afford হয় না → affordable খালি → 2-ই ফেরে। `k=0`-তে loop চলে না → 0। `k=10` কিন্তু project 3-টা → শেষে by_capital ও affordable খালি হয়ে break → 6। সব assert pass-এর পরে print হয়: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**O(n log n)** — প্রতিটা project বড়জোর একবার `by_capital` থেকে pop হয়ে `affordable`-এ push হয় (n-টা move, প্রতিটা O(log n)), আর বড়জোর `k` বার max profit pop। k ≤ n ধরলে মোট O(n log n)।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(n)** — দুই heap মিলে সব project ধরে রাখে। প্রতিটা project ঠিক একবার এক heap থেকে অন্যটায় যায়, একসাথে duplicate থাকে না, তাই memory project-সংখ্যার সমানুপাতিক।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- profit-কে max-heap না বানিয়ে সরাসরি heapq ব্যবহার — তখন তুমি সবচেয়ে **কম** profit-এর project নিচ্ছ, ভুল উত্তর।
- প্রতি round-এ পুরো list আবার scan/sort করা — capital শুধু বাড়ে বলে pointer শুধু সামনে এগোয়; বারবার scan নিখাদ অপচয় (O(k·n))।
- `affordable` খালি হলে `break` না দেওয়া — তখন খালি heap-এ pop করে IndexError, বা ভুলভাবে loop চালিয়ে যাওয়া।
- capital আর profit-এর order tuple-এ উল্টে ফেলা — heap তখন profit দিয়ে sort করবে, unlock logic ভেঙে যাবে।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি `08`-এর `concept.md`-র max-heap-via-negation আর `patterns.md`-র Pattern 6 (Heap + greedy combos) — "একটা greedy নিয়ম ঠিক করে কী নেবে, heap সেটা সস্তায় দেয়"। এখানে twist হলো **দুটো** heap: একটা unlock-এর জন্য (capital), একটা selection-এর জন্য (profit)। `001`-এর single-heap greedy এর সরল রূপ।
### পরের অনুশীলন {#22-similar-harder-problems}
- Find Median from Data Stream —