010 — Task Scheduler

Source

• Original source: Classic heap + greedy scheduling
• Platform: LeetCode — https://leetcode.com/problems/task-scheduler/
• Topic: heap / priority queue
• Difficulty: Medium
• Pattern: Heap + greedy (most frequent first)
• Basic idea inherited from: 05-hashing counting — task frequency গোনা, তারপর greedy দিয়ে সবচেয়ে frequent আগে চালানো

1. Problem in simple words

কতগুলো task দেওয়া আছে (অক্ষর দিয়ে চিহ্নিত) আর একটা cooldown সংখ্যা n। প্রতিটা time unit-এ CPU একটা task করে বা idle থাকে। শর্ত: একই task দুবার করার মাঝে অন্তত n unit গ্যাপ থাকতে হবে। সব task শেষ করতে সবচেয়ে কম কত unit সময় লাগবে (idle সহ), সেই সংখ্যাটা বের করো।

tasks = ["A","A","A","B","B","B"],  n = 2  ->  8 units
        (A B idle A B idle A B  ->  মোট 8)

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।

6. Real-life analogy

ভাবো একটা কারখানায় কয়েক ধরনের কাজ আছে, আর একই কাজ পরপর করলে মেশিন গরম হয়ে যায় — তাই মাঝে n unit বিশ্রাম লাগে। ফোরম্যান প্রতি দফায় সবচেয়ে বেশি বাকি-থাকা কাজগুলো আগে ধরেন (যাতে সেগুলো ছড়িয়ে যায়), আর এক দফায় একই কাজ দুবার দেন না। কোনো কাজ না থাকলে মেশিন কিছুক্ষণ idle। সেই "সবচেয়ে বেশি-বাকি কাজ চট করে দাও" যন্ত্রটাই max-heap।

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:

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

8. Example input and output

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   (সব আলাদা)

9. Brute force thinking

প্রথম সরল চিন্তা: time unit ধরে এগোও; প্রতি unit-এ এমন একটা task বেছে চালাও যেটার cooldown শেষ আর যেটা সবচেয়ে বেশি বাকি; কোনোটা ready না থাকলে idle। প্রতি unit-এ সব task স্ক্যান করে "কে ready আর সবচেয়ে frequent" খোঁজা।

প্রতি 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-র কথা মাথায় আসা উচিত।

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

15. Python solution

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 গোনা হয় না)।

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!।

18. Time complexity

O(total_tasks) কার্যত — প্রতিটা task একবার heap থেকে বের হয়, আর distinct task সংখ্যা m ছোট (alphabet)। heap ops O(log m) কিন্তু m ছোট fixed বলে নগণ্য; cycle-গুলো মিলিয়ে মোট কাজ মূলত total task সংখ্যার সমানুপাতিক। (একটা O(1) formula-based সমাধানও আছে, কিন্তু heap version pattern শেখায়।)

19. Space complexity

O(m) — m = distinct task সংখ্যা, heap আর temp-list দুটোই বড়জোর m entry ধরে। fixed alphabet-এ কার্যত O(1)।

20. Common mistakes

• max-heap না বানিয়ে min-heap ব্যবহার — তখন সবচেয়ে কম-frequent task আগে চলে, idle বেড়ে ভুল উত্তর।
• শেষ cycle-এও পুরো n+1 গোনা — heap খালি হয়ে গেলে পেছনে trailing idle গোনা উচিত না; তাই else ran।
• count 0 হয়ে যাওয়া task আবার heap-এ ফেরত দেওয়া — if cnt > 0 guard ছাড়া শেষ-হওয়া task-ও ঘুরতে থাকবে, infinite loop।

21. Which basic problem this inherits from

ভিত্তি 05-hashing-এর counting, আর 08-এর Pattern 6 (patterns.md) — "heap + greedy: always pick the most frequent next"। এটা #6/#8-এর frequency-counting আত্মীয়, কিন্তু এখানে greedy scheduling যোগ হয় — frequent task ছড়িয়ে idle কমানো।

22. Similar harder problems

• Reorganize String — https://leetcode.com/problems/reorganize-string/ (এই tracker-এর #11)
• Single-Threaded CPU — https://leetcode.com/problems/single-threaded-cpu/ (#13)
• Last Stone Weight — https://leetcode.com/problems/last-stone-weight/ (#1, একই "extreme টেনে নাও" ছাঁচ)

23. Pattern learned

Heap + greedy, most-frequent-first: "same item মাঝে cooldown, সবচেয়ে frequent কে ছড়াও" দেখলে — count করো, max-heap-এ ঢালো, প্রতি n+1-cycle-এ top-গুলো pop করে চালাও, বাকি থাকলে cycle শেষে ফেরত। greedy ঠিক করে কাকে আগে নেবে, heap সেটা সস্তায় দেয়। এই ছাঁচ Reorganize String-এ প্রায় হুবহু ফেরে।

24. Final summary

ভবিষ্যতের আমাকে: "task scheduler / cooldown gap" = Counter + max-heap of counts, প্রতি n+1-cycle-এ frequent গুলো চালাও আর বাকি ফেরত দাও; শেষ cycle-এ trailing idle গোনো না। মনে রেখো — idle-এর চাপ আসে সবচেয়ে frequent task থেকে, তাই তাকেই আগে ছড়াও। এটা heap + greedy scheduling-এর প্রতিনিধি।

25. JavaScript solution (with test cases)

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 করতে হতো)।

26. TypeScript solution (with test cases)

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<string, number>();
  for (const t of tasks) count.set(t, (count.get(t) ?? 0) + 1);
  const heap = new MaxHeap();
  for (const c of count.values()) heap.push(c);
  let time = 0;
  while (heap.size > 0) {
    const temp: number[] = [];
    let ran = 0;
    for (let i = 0; i < n + 1; i++) {
      if (heap.size > 0) {
        const cnt = heap.pop() - 1;
        ran++;
        if (cnt > 0) temp.push(cnt);
      }
    }
    for (const c of temp) heap.push(c);
    time += heap.size > 0 ? n + 1 : ran;
  }
  return time;
}

const expect = (cond: boolean, msg = ""): void => { if (!cond) throw new Error("FAIL " + msg); };

expect(leastInterval(["A", "A", "A", "B", "B", "B"], 2) === 8, "8");
expect(leastInterval(["A", "A", "A", "B", "B", "B"], 0) === 6, "6");
expect(leastInterval(["A", "A", "A", "A", "B"], 3) === 13, "13");
expect(leastInterval(["A", "B", "C", "D"], 2) === 4, "4");
expect(leastInterval(["A"], 5) === 1, "1");
console.log("সব TS test pass!");

TS টীকা: Map<string, number> typed — key task-নাম (string), value count (number); ভুল type ঢোকালে compile error। count.get(t) ?? 0-এ nullish-coalescing ?? ঠিকঠাক first-time undefined-কে 0 করে (|| 0-র চেয়ে নিরাপদ, যদিও count-এ পার্থক্য নেই)। private a: number[] heap-এ শুধু সংখ্যা নিশ্চিত করে।

27. কোথায় কাজে লাগে (real-world use)

• CPU / job scheduling: একই ধরনের কাজ পরপর না চালিয়ে cooldown মেনে frequent task ছড়িয়ে দেওয়া — throughput বাড়াতে ও resource contention কমাতে।
• Rate limiting / API throttling: একই client/endpoint-এ পরপর call-এর মাঝে gap রেখে সবচেয়ে চাহিদা-ওয়ালা request আগে কিন্তু ছড়িয়ে process করা।
• Cache eviction scheduling: frequently-accessed item-গুলো ছড়িয়ে refresh করা যাতে একসাথে অনেক miss না হয়।
• Manufacturing / machine cooldown: একই মেশিনে একই অপারেশন পরপর না করে তাপ/wear কমাতে cooldown gap রেখে scheduling।
• Message / notification spacing: একই ধরনের notification পরপর না পাঠিয়ে নির্দিষ্ট ব্যবধানে ছড়ানো (spam-feel কমাতে)।

মূল সুর: "একই item-এর মাঝে cooldown লাগে, আর সবচেয়ে frequent-টাকে ছড়াতে হবে" — count করো, max-heap-এ ঢালো, প্রতি window-তে frequent গুলো আগে চালাও।

---

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি নেই — এটা একটা common interview pattern।