013 — Single-Threaded CPU¶

Source¶

Original source: Classic event-simulation with a ready-queue heap
Platform: LeetCode — https://leetcode.com/problems/single-threaded-cpu/
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

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 করো।

tasks = [[1,2],[2,4],[3,2],[4,1]]  ->  order [0, 2, 3, 1]

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 এগিয়েই জানা যায়।

6. Real-life analogy¶

ভাবো একটা photocopy দোকানে একটাই machine। লোকজন বিভিন্ন সময়ে এসে লাইনে দাঁড়ায় (enqueueTime), প্রত্যেকের কাজের আকার আলাদা (processingTime)। দোকানদার নিয়ম করেছেন — machine খালি হলে এ পর্যন্ত হাজির লোকদের মধ্যে সবচেয়ে ছোট কাজ আগে; সমান হলে যে আগে এসেছিল (ছোট index)। কেউ না থাকলে পরের জন আসা অবধি অপেক্ষা। সেই "সবচেয়ে ছোট কাজ চট করে দাও" line-টাই min-heap।

7. Visual explanation¶

tasks = [[1,2],[2,4],[3,2],[4,1]] (index সহ), enqueue দিয়ে sort করা আছে:

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]

8. Example input and output¶

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)

9. Brute force thinking¶

প্রথম সরল চিন্তা: একটা ঘড়ি now রাখো; প্রতিবার CPU free হলে সব task scan করে যেগুলো enqueueTime <= now তাদের মধ্যে min (processingTime, index) খুঁজে নাও; চালাও; repeat।

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 চিন্তা)।

14. Step-by-step dry run¶

Input tasks = [[5,3],[1,1]] (index 0,1):

index সহ sort by enqueue → [(1,1,idx1), (5,3,idx0)]; now=0, i=0, heap empty, order=[]
heap খালি, কোনো task enqueue<=0 নেই → now লাফ দিয়ে 1 (task idx1-এর enqueue)
enqueue<=1: task idx1 (proc 1) heap-এ → heap {(1,1)}; pop (1,1) → order [1], now=1+1=2
enqueue<=2: কেউ নেই; heap খালি → now লাফ দিয়ে 5 (task idx0-এর enqueue)
enqueue<=5: task idx0 (proc 3) heap-এ → heap {(3,0)}; pop (3,0) → order [1,0], now=5+3=8
সব task শেষ → return [1, 0]

15. Python solution¶

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 হওয়া অবধি চলে।

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

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।

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 — https://leetcode.com/problems/meeting-rooms-ii/ (এই tracker-এর #9; scheduling, end-time heap)
Task Scheduler — https://leetcode.com/problems/task-scheduler/ (#10; cooldown-সহ greedy scheduling)
Process Tasks Using Servers — https://leetcode.com/problems/process-tasks-using-servers/ (দুই heap দিয়ে server assignment simulation)

23. Pattern learned¶

Scheduling by simulation: দুটো order আলাদা করো — কে কখন ready হয় (sort by availability + pointer) আর কে আগে চলবে (min-heap of priority)। সময়কে event-এ লাফাও, idle tick গুনো না। CPU/machine/server-এর "next job" বাছাইয়ের প্রায় সব problem এই ছাঁচে পড়ে।

24. Final summary¶

ভবিষ্যতের আমাকে: "একটাই CPU, shortest job first, tie → index, available হওয়া অবধি wait" = enqueue দিয়ে sort + (proc, index) min-heap + একটা ঘড়ি যেটা কাজ-শেষে এগোয় বা idle-তে লাফায়। Meeting Rooms II আর Task Scheduler-এর সাথে একই scheduling পরিবারে — একটা ধরলে বাকিগুলোও চেনা লাগে।

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