010 — Task Scheduler

অধ্যায় · সমস্ত অনুশীলন ও উৎস · ধাপে ধাপে শেখা

Problem link ও উৎস

• 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 আগে চালানো

প্রশ্ন ও উদাহরণ

সহজ করে প্রশ্ন

কতগুলো 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)

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

চেনা উদাহরণে বোঝা

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

ভিত্তির ধারণা

আগের কোন ধারণাটি লাগবে

ভিত হলো 05-hashing-এর counting — কোন task কতবার আছে গোনা। তারপর 08-এর heap + greedy: প্রতিটা cooldown-cycle-এ সবচেয়ে বেশি-বাকি task গুলো আগে চালানো, যাতে busy frequent task গুলো ছড়িয়ে যায় আর idle কমে। অর্থাৎ "count, then greedily run the most frequent".

ভেতরের যুক্তি

লুকানো logic একটা greedy invariant: যে task সবচেয়ে বেশিবার বাকি, তাকে সবচেয়ে আগে আর সবচেয়ে ঘনঘন চালাও (cooldown মেনে)। কারণ frequent task-ই idle তৈরির মূল চাপ — তাকে যত তাড়াতাড়ি ছড়িয়ে দেবে, ফাঁকগুলো তত ভালো ভরবে। প্রতি n+1-দৈর্ঘ্যের window-তে যত বেশি distinct frequent task বসাতে পারবে, idle তত কম।

কী দিয়ে তথ্য রাখব

একটা max-heap of remaining counts (frequency)। heapq min-heap, তাই count negate করি — top-এ থাকে সবচেয়ে বেশি-বাকি task। সাথে প্রতি cycle-এ যেগুলো এখনো বাকি কিন্তু cooldown-এ আছে, তাদের সাময়িকভাবে একটা list-এ রেখে cycle শেষে heap-এ ফেরত দিই।

এটি কেন উপযুক্ত

প্রতি 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।

ধাপে ধাপে সমাধান

প্রথম সরল উপায়

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

উদাহরণ

প্রতি time unit-এ: সব task দেখো -> ready + max remaining বাছো -> চালাও বা idle

কোথায় বেশি কাজ হচ্ছে

প্রতি time unit-এ সব distinct task স্ক্যান করা মানে total time × m কাজ; বড় count আর বড় n-এ total time অনেক, তাই O(total_time × m) — অপ্রয়োজনীয় ধীর। max-heap "সবচেয়ে frequent ready task" সরাসরি দেয় বলে প্রতি cycle-এ স্ক্যানের দরকার পড়ে না।

যে বিষয়টি খেয়াল করতে হবে

মূল observation: idle তৈরির আসল চাপ আসে সবচেয়ে frequent task থেকে — তাকে যত আগে আর যত ছড়িয়ে চালাবে, ফাঁক তত ভরবে। তাই প্রতি n+1-দৈর্ঘ্যের cycle-এ সবচেয়ে frequent বাকি task গুলো আগে বসাও; এক cycle-এ একই task দুবার নয়।

আরও কম কাজে সমাধান

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 খালি হলে থামো।

ভাবনার পরিবর্তন

মোচড়: "schedule কীভাবে সাজাব" না ভেবে ভাবো "প্রতি cooldown-window-তে সবচেয়ে frequent বাকি task গুলো ভরছি, ফাঁক থাকলে idle।" যখনই দেখবে "same item মাঝে গ্যাপ লাগে, সবচেয়ে frequent কে ছড়াতে হবে", তখন max-heap + cycle-by-cycle greedy-র কথা মাথায় আসা উচিত।

ছবিতে বোঝা

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

ছোট input-এ ধাপে ধাপে

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

কোড ও ব্যাখ্যা

Python

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!")

কোডের প্রতিটি অংশ

• 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 মিলিয়ে দেখা

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

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

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<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-এ শুধু সংখ্যা নিশ্চিত করে।

খরচ ও সাধারণ ভুল

সময়

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 শেখায়।)

অতিরিক্ত জায়গা

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

যে ভুলগুলো এড়াতে হবে

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

শেখা ও পরের অনুশীলন

ভিত্তির সঙ্গে সম্পর্ক

ভিত্তি 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 কমানো।

পরের অনুশীলন

• 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 টেনে নাও" ছাঁচ)

কৌশলটি মনে রাখুন

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

নিজেকে যাচাই করুন

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

কোথায় কাজে লাগে

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