Problem link ও উৎস
- **Original source:** Classic event-simulation with a ready-queue heap
- **Platform:** LeetCode —
- **Topic:** heap / priority queue
- **Difficulty:** Medium
- **Pattern:** Scheduling / simulation (sort by availability + min-heap of ready jobs)
- **Basic idea inherited from:** `04-stack-and-queue` queue thinking — কে আগে কাজ পাবে; তারপর `08` min-heap
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
কতগুলো task দেওয়া, প্রতিটার দুটো মান: `enqueueTime` (কখন task-টা available হয়) আর `processingTime` (চালাতে কত সময় লাগে)। একটাই CPU; সে একসাথে একটাই task চালায়। CPU free হলে, এ পর্যন্ত available task-গুলোর মধ্যে **সবচেয়ে কম processing time-ওয়ালা** নেয়; tie হলে **ছোট index** আগে। কোনো task available না থাকলে CPU অপেক্ষা করে পরের available হওয়া অবধি। সব task যে **order-এ process হয়** সেই index-গুলোর list return করো।
```text
tasks = [[1,2],[2,4],[3,2],[4,1]] -> order [0, 2, 3, 1]
```
### Input ও output {#8-example-input-and-output}
```text
Input : tasks = [[1,2],[2,4],[3,2],[4,1]] -> Output: [0, 2, 3, 1]
Input : tasks = [[7,10],[7,12],[7,5],[7,4],[7,2]] -> Output: [4, 3, 2, 0, 1]
Input : tasks = [[1,2]] -> Output: [0]
Input : tasks = [[5,3],[1,1]] -> Output: [1, 0] (index 1 আগে available)
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো একটা photocopy দোকানে একটাই machine। লোকজন বিভিন্ন সময়ে এসে লাইনে দাঁড়ায় (enqueueTime), প্রত্যেকের কাজের আকার আলাদা (processingTime)। দোকানদার নিয়ম করেছেন — machine খালি হলে এ পর্যন্ত হাজির লোকদের মধ্যে **সবচেয়ে ছোট কাজ** আগে; সমান হলে যে আগে এসেছিল (ছোট index)। কেউ না থাকলে পরের জন আসা অবধি অপেক্ষা। সেই "সবচেয়ে ছোট কাজ চট করে দাও" line-টাই min-heap।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
ভিত দুটো। `04-stack-and-queue`-এর **queue thinking** — কাজগুলো এসে একটা "ready" line-এ দাঁড়ায়, কে আগে service পাবে সেটা ঠিক করতে হয়। কিন্তু এখানে FIFO নয়, **priority** (সবচেয়ে ছোট processing time)। তাই plain queue-র জায়গায় `08`-এর **min-heap** বসে, যেটা priority-ordered queue।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic একটা **event-driven simulation** + একটা **greedy choice**। সময়কে এগিয়ে নাও; প্রতিটা মুহূর্তে যে task-গুলোর `enqueueTime <= now` তারা "ready"। CPU free হলে greedy: ready-দের মধ্যে সবচেয়ে ছোট `processingTime` (tie → ছোট index) নাও — এটা মোট কাজ সাজানোর জন্য locally-best, কারণ ছোট কাজ আগে শেষ করলে বেশি কাজ early available হয়।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
দুটো। (1) task-গুলোকে **`enqueueTime` দিয়ে sort** করা একটা list (কে কখন ready হয় জানতে)। (2) একটা **min-heap of `(processingTime, index)`** — ready task-দের ধরে রাখে, top = পরের চালানো উচিত task।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
ready task-দের মধ্যে বারবার "সবচেয়ে ছোট processingTime (tie → index)" লাগে — পুরো sorted order না। `(processingTime, index)` tuple-এর min-heap ঠিক সেটাই দেয়: peek O(1)-সম, pop/push O(log n)। sorted-by-enqueue list বলে কোন task এখন ready হয়েছে সেটা এক pointer এগিয়েই জানা যায়।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: একটা ঘড়ি `now` রাখো; প্রতিবার CPU free হলে **সব task scan** করে যেগুলো `enqueueTime <= now` তাদের মধ্যে min `(processingTime, index)` খুঁজে নাও; চালাও; repeat।
```text
free -> সব task ঘেঁটে ready দের মধ্যে smallest খোঁজো -> চালাও -> আবার ঘাঁটো
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
প্রতিবার পুরো list scan মানে প্রতি selection-এ O(n), আর selection হয় n-টা — মোট **O(n²)**। n বড় হলে এটা ধীর। অথচ "ready-দের মধ্যে min" প্রশ্নটা একটা heap O(log n)-এই দেয়, আর কোন task ready হলো সেটা sorted list-এ এক pointer এগিয়েই ধরা যায়।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: দুটো আলাদা order মেশানো আছে — task-রা **enqueue order**-এ ready হয়, কিন্তু **processingTime order**-এ চলে। প্রথমটা handle করো enqueue-sorted list + একটা pointer দিয়ে; দ্বিতীয়টা handle করো min-heap দিয়ে। CPU idle থাকলে সময়কে পরের available task-এ লাফ দাও — খালি খালি tick গুনো না।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
Task-দের index মনে রেখে `enqueueTime` দিয়ে sort করো। একটা pointer `i`, একটা ঘড়ি `now`, একটা min-heap। Loop যতক্ষণ কাজ বাকি: `enqueueTime <= now` সব task heap-এ ঢালো; heap খালি হলে `now`-কে পরের task-এর enqueue-এ লাফ দাও; নাহলে heap থেকে `(proc, idx)` pop করে order-এ idx যোগ করো, `now += proc`। এক pass, প্রতিটা task একবার heap-এ ঢোকে-বেরোয়।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "CPU scheduling" না ভেবে ভাবো "একটা ready-pool থেকে বারবার সবচেয়ে ছোট কাজ টানছি, আর সময় হয় এগোয় কাজ-শেষে, নয়তো লাফায় idle হলে।" "machine/CPU picks next job / available হওয়া অবধি wait / shortest job first" — এমন কথা শুনলেই sort-by-availability + min-heap-এর কথা মাথায় আসা উচিত (Pattern 4-এর scheduling চিন্তা)।
### ছবিতে বোঝা {#7-visual-explanation}
`tasks = [[1,2],[2,4],[3,2],[4,1]]` (index সহ), enqueue দিয়ে sort করা আছে:
```text
time=0: কেউ ready নেই -> time লাফ দিয়ে 1 (প্রথম enqueue)
time=1: ready {(2,0)} -> pop (2,0): চালাও task 0, শেষ time=1+2=3 order[0]
time=3: ready {(4,1),(2,2)} -> pop (2,2): চালাও task 2, শেষ time=3+2=5 order[0,2]
time=5: ready {(4,1),(1,3)} -> pop (1,3): চালাও task 3, শেষ time=5+1=6 order[0,2,3]
time=6: ready {(4,1)} -> pop (4,1): চালাও task 1, শেষ time=6+4=10 order[0,2,3,1]
final order: [0, 2, 3, 1]
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input `tasks = [[5,3],[1,1]]` (index 0,1):
1. index সহ sort by enqueue → `[(1,1,idx1), (5,3,idx0)]`; `now=0`, `i=0`, heap empty, order=[]
2. heap খালি, কোনো task `enqueue<=0` নেই → `now` লাফ দিয়ে 1 (task idx1-এর enqueue)
3. `enqueue<=1`: task idx1 (proc 1) heap-এ → heap {(1,1)}; pop (1,1) → order [1], `now=1+1=2`
4. `enqueue<=2`: কেউ নেই; heap খালি → `now` লাফ দিয়ে 5 (task idx0-এর enqueue)
5. `enqueue<=5`: task idx0 (proc 3) heap-এ → heap {(3,0)}; pop (3,0) → order [1,0], `now=5+3=8`
6. সব task শেষ → return [1, 0]
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
import heapq
def get_order(tasks):
# প্রতিটা task-এ আসল index জুড়ে enqueueTime দিয়ে sort
indexed = sorted(range(len(tasks)), key=lambda i: tasks[i][0])
order = []
heap = [] # (processingTime, index) — ready task-রা
now = 0
i = 0 # indexed-এ পরের কোন task ঢোকানো বাকি
n = len(tasks)
while len(order) < n:
# এ পর্যন্ত available সব task heap-এ ঢালো
while i < n and tasks[indexed[i]][0] <= now:
enq, proc = tasks[indexed[i]]
heapq.heappush(heap, (proc, indexed[i]))
i += 1
if not heap: # CPU idle: পরের task-এ সময় লাফ দাও
now = tasks[indexed[i]][0]
continue
proc, idx = heapq.heappop(heap) # shortest job, tie -> ছোট index
order.append(idx)
now += proc # CPU ওই task-এ busy থাকে
return order
# ---- tests ----
assert get_order([[1, 2], [2, 4], [3, 2], [4, 1]]) == [0, 2, 3, 1]
assert get_order([[7, 10], [7, 12], [7, 5], [7, 4], [7, 2]]) == [4, 3, 2, 0, 1]
assert get_order([[1, 2]]) == [0] # একটাই task
assert get_order([[5, 3], [1, 1]]) == [1, 0] # index 1 আগে available
assert get_order([[0, 1], [0, 1], [0, 1]]) == [0, 1, 2] # tie -> index order
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `indexed = sorted(range(n), key=...)` — task-দের আসল index, enqueueTime অনুযায়ী sort করা; tie-তে index ছোট থাকে (stable sort)।
- `heap = []` — ready task-দের `(processingTime, index)` min-heap; tuple বলে tie-তে index আপনাআপনি tie-break করে।
- `while i < n and tasks[indexed[i]][0] <= now:` — এখন পর্যন্ত available সব task heap-এ যোগ; pointer `i` শুধু সামনে এগোয়।
- `if not heap: now = tasks[indexed[i]][0]` — CPU idle হলে সময়কে পরের enqueue-এ লাফ দাও (idle tick গুনি না)।
- `proc, idx = heappop(heap)` — ready-দের মধ্যে shortest job (tie → ছোট index)।
- `order.append(idx); now += proc` — সেই task চালাও; CPU busy থাকে `proc` সময়।
- `while len(order) < n` — সব task process হওয়া অবধি চলে।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`get_order([[5,3],[1,1]])` section 14-এর dry run মেনে [1, 0] দেয় — assert pass। main example [0,2,3,1]; same-enqueue example processingTime অনুযায়ী [4,3,2,0,1]; all-tie `[[0,1]×3]` index order [0,1,2]। output একটা নির্দিষ্ট order (deterministic tie-break), তাই সরাসরি সমতা assert। সব pass-এর পরে print হয়: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**O(n log n)** — initial sort O(n log n); তারপর প্রতিটা task ঠিক একবার heap-এ push আর একবার pop হয় (প্রতিটা O(log n)), idle-jump গুলো অতিরিক্ত step যোগ করে না। তাই overall O(n log n)।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(n)** — `indexed` list, heap (বড়জোর n entry), আর output `order`। সব মিলিয়ে input-এর সমানুপাতিক।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- index track না করা — sort করার পর আসল index হারিয়ে গেলে ভুল order return হয়।
- tie-break ভুলে যাওয়া — heap-এ শুধু `processingTime` রাখলে সমান proc-এ ভুল index আগে আসতে পারে; `(proc, index)` রাখো।
- idle হলে সময় লাফ না দিয়ে এক এক করে tick করা — TLE হতে পারে আর infinite loop-ও বানাতে পারো।
- heap খালি অবস্থায় pop করা — আগে idle-jump করো, নাহলে IndexError।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি `04-stack-and-queue`-এর queue thinking (একটা ready line, কে আগে service পাবে) আর `08`-এর min-heap। আর `patterns.md`-র Pattern 4 (Earliest end / scheduling)-এর ভাইপো — সেখানে end-time দিয়ে room গুনি, এখানে processingTime দিয়ে CPU-র next job বাছি।
### পরের অনুশীলন {#22-similar-harder-problems}
- Meeting Rooms II —