Problem link ও উৎস
- **Original source:** Classic heap + greedy scheduling
- **Platform:** LeetCode —
- **Topic:** heap / priority queue
- **Difficulty:** Medium
- **Pattern:** Heap + greedy (most frequent first)
- **Basic idea inherited from:** `05-hashing` counting — task frequency গোনা, তারপর greedy দিয়ে সবচেয়ে frequent আগে চালানো
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
কতগুলো task দেওয়া আছে (অক্ষর দিয়ে চিহ্নিত) আর একটা cooldown সংখ্যা `n`। প্রতিটা time unit-এ CPU একটা task করে বা idle থাকে। শর্ত: **একই task দুবার করার মাঝে অন্তত `n` unit গ্যাপ** থাকতে হবে। সব task শেষ করতে **সবচেয়ে কম কত unit সময়** লাগবে (idle সহ), সেই সংখ্যাটা বের করো।
```text
tasks = ["A","A","A","B","B","B"], n = 2 -> 8 units
(A B idle A B idle A B -> মোট 8)
```
### Input ও output {#8-example-input-and-output}
```text
Input : tasks = ["A","A","A","B","B","B"], n = 2 -> Output: 8
Input : tasks = ["A","A","A","B","B","B"], n = 0 -> Output: 6 (cooldown নেই)
Input : tasks = ["A","A","A","A","B"], n = 3 -> Output: 13
Input : tasks = ["A","B","C","D"], n = 2 -> Output: 4 (সব আলাদা)
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো একটা কারখানায় কয়েক ধরনের কাজ আছে, আর একই কাজ পরপর করলে মেশিন গরম হয়ে যায় — তাই মাঝে `n` unit বিশ্রাম লাগে। ফোরম্যান প্রতি দফায় সবচেয়ে বেশি বাকি-থাকা কাজগুলো আগে ধরেন (যাতে সেগুলো ছড়িয়ে যায়), আর এক দফায় একই কাজ দুবার দেন না। কোনো কাজ না থাকলে মেশিন কিছুক্ষণ idle। সেই "সবচেয়ে বেশি-বাকি কাজ চট করে দাও" যন্ত্রটাই max-heap।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
ভিত হলো `05-hashing`-এর **counting** — কোন task কতবার আছে গোনা। তারপর `08`-এর **heap + greedy**: প্রতিটা cooldown-cycle-এ সবচেয়ে বেশি-বাকি task গুলো আগে চালানো, যাতে busy frequent task গুলো ছড়িয়ে যায় আর idle কমে। অর্থাৎ "count, then greedily run the most frequent".
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic একটা greedy invariant: **যে task সবচেয়ে বেশিবার বাকি, তাকে সবচেয়ে আগে আর সবচেয়ে ঘনঘন চালাও** (cooldown মেনে)। কারণ frequent task-ই idle তৈরির মূল চাপ — তাকে যত তাড়াতাড়ি ছড়িয়ে দেবে, ফাঁকগুলো তত ভালো ভরবে। প্রতি `n+1`-দৈর্ঘ্যের window-তে যত বেশি distinct frequent task বসাতে পারবে, idle তত কম।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
একটা **max-heap of remaining counts** (frequency)। heapq min-heap, তাই count negate করি — top-এ থাকে সবচেয়ে বেশি-বাকি task। সাথে প্রতি cycle-এ যেগুলো এখনো বাকি কিন্তু cooldown-এ আছে, তাদের সাময়িকভাবে একটা list-এ রেখে cycle শেষে heap-এ ফেরত দিই।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
প্রতি cooldown-cycle-এ একটাই প্রশ্ন বারবার: "এখন সবচেয়ে বেশি-বাকি task কে?" — max-heap top O(1)/pop O(log m)-এ দেয় (m = distinct task)। এক cycle-এ বড়জোর `n+1` টা ভিন্ন task pop করে চালাই, count কমিয়ে বাকি থাকলে temp-এ রাখি, cycle শেষে আবার push। এই "frequent টেনে নাও, কমাও, ফেরত দাও" loop-ই heap + greedy-র signature।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: time unit ধরে এগোও; প্রতি unit-এ এমন একটা task বেছে চালাও যেটার cooldown শেষ আর যেটা সবচেয়ে বেশি বাকি; কোনোটা ready না থাকলে idle। প্রতি unit-এ সব task স্ক্যান করে "কে ready আর সবচেয়ে frequent" খোঁজা।
```text
প্রতি time unit-এ: সব task দেখো -> ready + max remaining বাছো -> চালাও বা idle
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
প্রতি time unit-এ সব distinct task স্ক্যান করা মানে total time × m কাজ; বড় count আর বড় `n`-এ total time অনেক, তাই **O(total_time × m)** — অপ্রয়োজনীয় ধীর। max-heap "সবচেয়ে frequent ready task" সরাসরি দেয় বলে প্রতি cycle-এ স্ক্যানের দরকার পড়ে না।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: idle তৈরির আসল চাপ আসে **সবচেয়ে frequent task** থেকে — তাকে যত আগে আর যত ছড়িয়ে চালাবে, ফাঁক তত ভরবে। তাই প্রতি `n+1`-দৈর্ঘ্যের cycle-এ সবচেয়ে frequent বাকি task গুলো আগে বসাও; এক cycle-এ একই task দুবার নয়।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
count গোনো, max-heap-এ ঢালো। loop: প্রতি cycle-এ বড়জোর `n+1` বার top pop করো, প্রতিটা চালাও (count−1), বাকি থাকলে temp-list-এ রাখো; cycle শেষে temp থেকে heap-এ ফেরত push করো। যদি heap এখনো non-empty থাকে তবে এই cycle পুরো `n+1` unit (idle সহ) গোনো, নাহলে শুধু যতগুলো task চালিয়েছ তত। heap খালি হলে থামো।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "schedule কীভাবে সাজাব" না ভেবে ভাবো "প্রতি cooldown-window-তে সবচেয়ে frequent বাকি task গুলো ভরছি, ফাঁক থাকলে idle।" যখনই দেখবে "same item মাঝে গ্যাপ লাগে, সবচেয়ে frequent কে ছড়াতে হবে", তখন max-heap + cycle-by-cycle greedy-র কথা মাথায় আসা উচিত।
### ছবিতে বোঝা {#7-visual-explanation}
`tasks = ["A","A","A","B","B","B"]`, `n = 2`। count {A:3, B:3}। প্রতি cycle = `n+1` = 3 unit; max-heap-এ remaining counts:
```text
counts: A:3, B:3 cycle length = n+1 = 3
cycle 1: pop A(3)->run, pop B(3)->run, কেউ বাকি নেই এই cycle-এ -> idle
schedule: A B _ time so far = 3 | বাকি A:2, B:2
cycle 2: pop A(2)->run, pop B(2)->run, idle
schedule: A B _ time so far = 6 | বাকি A:1, B:1
cycle 3: pop A(1)->run, pop B(1)->run, heap খালি -> idle লাগে না (শেষ cycle)
schedule: A B time so far = 8 | বাকি কিছু নেই
মোট time = 8
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input `tasks = ["A","A","A","B","B","B"]`, `n = 2` (cycle = 3):
1. count {A:3, B:3} → max-heap {3, 3}, time = 0
2. cycle 1: pop A→2, pop B→2 (দুটো চালানো হলো); heap এই cycle-এ আর নেই → temp {2,2}; heap non-empty হবে → time += 3 → time = 3; temp ফেরত → heap {2,2}
3. cycle 2: pop A→1, pop B→1; temp {1,1}; heap non-empty → time += 3 → time = 6; ফেরত → heap {1,1}
4. cycle 3: pop A→0, pop B→0; temp খালি (count 0 ফেরত না); heap এখন খালি → শুধু চালানো 2 unit → time += 2 → time = 8
5. heap খালি → return 8
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
import heapq
from collections import Counter
def least_interval(tasks, n):
counts = list(Counter(tasks).values()) # প্রতিটা task কতবার বাকি
heap = [-c for c in counts] # max-heap: count negate
heapq.heapify(heap) # top = সবচেয়ে বেশি-বাকি task
time = 0
while heap:
temp = [] # এই cycle-এ চালানো, এখনো বাকি
ran = 0 # এই cycle-এ কয়টা task চালালাম
# এক cooldown-cycle = n+1 slot, প্রতি slot-এ বড়জোর একটা distinct task
for _ in range(n + 1):
if heap:
cnt = -heapq.heappop(heap) - 1 # একবার চালালাম, বাকি কমল
ran += 1
if cnt > 0:
temp.append(-cnt) # এখনো বাকি -> পরে ফেরত
for c in temp:
heapq.heappush(heap, c) # cycle শেষে বাকিগুলো ফেরত
# heap এখনো বাকি থাকলে এই cycle পুরো n+1 (শেষ slot পর্যন্ত idle গোনা);
# heap খালি হলে শুধু যতগুলো task চালিয়েছি তত unit (পেছনে idle নয়)
time += (n + 1) if heap else ran
return time
# ---- tests ----
assert least_interval(["A", "A", "A", "B", "B", "B"], 2) == 8
assert least_interval(["A", "A", "A", "B", "B", "B"], 0) == 6 # cooldown নেই
assert least_interval(["A", "A", "A", "A", "B"], 3) == 13
assert least_interval(["A", "B", "C", "D"], 2) == 4 # সব আলাদা
assert least_interval(["A"], 5) == 1 # একটাই task
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `counts = list(Counter(tasks).values())` — `05-hashing`-এর counting; task-এর নাম ভুলে শুধু কে কতবার আছে দরকার।
- `heap = [-c for c in counts]` + `heapify` — count negate করে max-heap; top = সবচেয়ে বেশি-বাকি task।
- `for _ in range(n + 1):` — এক cooldown-cycle-এ ঠিক `n+1` slot; প্রতি slot-এ বড়জোর একটা distinct task।
- `cnt = -heapq.heappop(heap) - 1` — সবচেয়ে frequent টা একবার চালালাম, তাই count এক কমল।
- `ran += 1` — এই cycle-এ আসলে কয়টা task চালানো হলো (idle গোনার জন্য দরকার)।
- `if cnt > 0: temp.append(-cnt)` — এখনো বাকি থাকলে temp-এ রাখি, cycle-এর মধ্যে আবার যেন না আসে।
- `for c in temp: heapq.heappush(...)` — cycle শেষে বাকি task গুলো heap-এ ফেরত।
- `time += (n + 1) if heap else ran` — heap-এ আরও task বাকি থাকলে এই cycle পুরো `n+1` (idle সহ); শেষ cycle-এ heap খালি হলে শুধু চালানো `ran` unit (পেছনে idle গোনা হয় না)।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`least_interval(["A","A","A","B","B","B"],2)` section 14 মেনে 8 দেয় — assert pass। `n=0` মানে cooldown নেই → প্রতি cycle 1 unit, কখনো idle না → 6। `["A","A","A","A","B"],3` → A সবচেয়ে frequent (4 বার), ফাঁক ভরাতে অনেক idle → 13। `["A","B","C","D"],2` → সব আলাদা, cooldown কখনো লাগে না → 4। `["A"],5` → একটাই → 1। পাঁচটা assert pass করার পরে print হয়: `সব test pass!`।
### JavaScript ও test cases {#25-javascript-solution-with-test-cases}
```javascript
const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };
// Node-এ built-in heap নেই; সংখ্যার একটা minimal MaxHeap (top = সবচেয়ে বড়)
class MaxHeap {
constructor() { this.a = []; }
get size() { return this.a.length; }
push(x) {
const a = this.a; a.push(x);
let i = a.length - 1;
while (i > 0) {
const p = (i - 1) >> 1;
if (a[p] >= a[i]) break;
[a[p], a[i]] = [a[i], a[p]]; i = p;
}
}
pop() {
const a = this.a, top = a[0], last = a.pop();
if (a.length) {
a[0] = last; let i = 0;
while (true) {
const l = 2 * i + 1, r = 2 * i + 2; let big = i;
if (l < a.length && a[l] > a[big]) big = l;
if (r < a.length && a[r] > a[big]) big = r;
if (big === i) break;
[a[big], a[i]] = [a[i], a[big]]; i = big;
}
}
return top;
}
}
function leastInterval(tasks, n) {
const count = new Map();
for (const t of tasks) count.set(t, (count.get(t) || 0) + 1); // frequency গোনা
const heap = new MaxHeap();
for (const c of count.values()) heap.push(c); // max-heap: top = সবচেয়ে বেশি-বাকি
let time = 0;
while (heap.size > 0) {
const temp = []; // এই cycle-এ চালানো, এখনো বাকি
let ran = 0; // এই cycle-এ কয়টা task চালালাম
for (let i = 0; i < n + 1; i++) { // এক cooldown-cycle = n+1 slot
if (heap.size > 0) {
const cnt = heap.pop() - 1; // একবার চালালাম, বাকি কমল
ran++;
if (cnt > 0) temp.push(cnt); // এখনো বাকি → পরে ফেরত
}
}
for (const c of temp) heap.push(c); // cycle শেষে বাকিগুলো ফেরত
// heap বাকি থাকলে পুরো n+1 (idle সহ); নাহলে শুধু চালানো ran unit
time += heap.size > 0 ? n + 1 : ran;
}
return time;
}
// ---- test cases ----
assert(leastInterval(["A", "A", "A", "B", "B", "B"], 2) === 8, "basic");
assert(leastInterval(["A", "A", "A", "B", "B", "B"], 0) === 6, "cooldown নেই");
assert(leastInterval(["A", "A", "A", "A", "B"], 3) === 13, "ভারী A");
assert(leastInterval(["A", "B", "C", "D"], 2) === 4, "সব আলাদা");
assert(leastInterval(["A"], 5) === 1, "একটাই task");
console.log("সব JS test pass!");
```
> **JS টীকা:** দুটো জিনিস JS-এ আলাদা: (১) **built-in heap নেই**, তাই সংখ্যার max-heap হাতে লিখলাম; (২) Python-এর `Counter`-এর সমতুল্য হলো `Map` — `count.get(t) || 0` দিয়ে first-time key 0 ধরা হয়। heap negate করার দরকার নেই কারণ এটা সরাসরি max-heap (Python-এ min-heap বলে count negate করতে হতো)।
### TypeScript ও test cases {#26-typescript-solution-with-test-cases}
```typescript
class MaxHeap {
private a: number[] = [];
get size(): number { return this.a.length; }
push(x: number): void {
const a = this.a; a.push(x);
let i = a.length - 1;
while (i > 0) {
const p = (i - 1) >> 1;
if (a[p] >= a[i]) break;
[a[p], a[i]] = [a[i], a[p]]; i = p;
}
}
pop(): number {
const a = this.a, top = a[0], last = a.pop() as number;
if (a.length) {
a[0] = last; let i = 0;
while (true) {
const l = 2 * i + 1, r = 2 * i + 2; let big = i;
if (l < a.length && a[l] > a[big]) big = l;
if (r < a.length && a[r] > a[big]) big = r;
if (big === i) break;
[a[big], a[i]] = [a[i], a[big]]; i = big;
}
}
return top;
}
}
function leastInterval(tasks: string[], n: number): number {
const count = new Map