গ্রিডি অ্যালগরিদম৬ মিনিট পড়া

টাস্ক শিডিউলিং (Task Scheduling)

কাছের ডেডলাইন অনুযায়ী আগে কাজ করুন — কোনো কাজ মিস হবে না, সবচেয়ে বেশি লাভ হবে
time:দ্রুতগতিসম্পন্ন · O(n log n)space:লিনিয়ার · O(n)key insight:লাভের বা প্রফিটের (profit) ভিত্তিতে সাজান; ফাঁকা স্লট খোঁজার জন্য ইউনিয়ন-ফাইন্ড (Union-Find) ব্যবহার করুন

ধরুন রবিবার রাত, আর আপনার কাছে একগাদা অ্যাসাইনমেন্ট বা বাড়ির কাজ জমা পড়েছে। প্রতিটি ডেডলাইনের মধ্যে জমা দিতে পারলে আপনি পয়েন্ট পাবেন, এবং প্রতিটি কাজের জন্য ঠিক এক ঘণ্টা সময় লাগবে। আপনি একবারে কেবল একটি কাজই করতে পারবেন। আপনি কোন কাজগুলো আগে করবেন?

আপনি যদি বুদ্ধিমান হন: তবে সবচেয়ে বেশি লাভজনক কাজটি আগে বেছে নেবেন। সেটির ডেডলাইনের ঠিক আগের সর্বশেষ ফাঁকা স্লটে (latest available slot) কাজ শুরু করার রুটিন করবেন (যাতে আপনি অন্যান্য কাজের জন্য আগের স্লটগুলো ফাঁকা রাখতে পারেন)। যে কাজের জন্য আর কোনো ফাঁকা স্লট অবশিষ্ট নেই, সেটি বাদ দেবেন।

এক প্যারায় বলতে গেলে, এটিই হলো ডেডলাইনসহ টাস্ক শিডিউলিং। এর প্রধান কৌশলটি হলো "সর্বশেষ ফাঁকা স্লটটি খুঁজে বের করার" ধাপটিকে দ্রুত করা।

সমস্যাটির আনুষ্ঠানিক বর্ণনা (Formalising the Problem)

আপনার কাছে n সংখ্যক ইউনিট-টাইম টাস্ক (unit-time tasks) বা এক-ঘণ্টার কাজ আছে (প্রতিটি কাজে ঠিক ১টি টাইম স্লট লাগে)। টাস্ক i-এর জন্য আছে:
• ডেডলাইন d_i — অবশ্যই টাইম স্লট 1 থেকে d_i এর মধ্যে সম্পন্ন করতে হবে
• প্রফিট বা লাভ p_i — কেবল ডেডলাইনের মধ্যে শেষ করলেই লাভ হবে

আপনি প্রতি স্লটে সর্বাধিক একটি কাজ সম্পাদন করতে পারবেন। উদ্দেশ্য: মোট লাভ সর্বোচ্চ করার জন্য কোন কাজগুলো চালাবেন তা বেছে নেওয়া।

গ্রিডি পদ্ধতি (The Greedy Strategy)

১. টাস্কগুলোকে লাভের (profit) ক্রমানুসারে বড় থেকে ছোটতে সাজান (descending order)।
২. প্রতিটি টাস্কের জন্য (লাভের ক্রমানুসারে), এর ডেডলাইনের সমান বা ঠিক আগের সর্বশেষ ফাঁকা স্লটটি (latest free slot) খুঁজে বের করুন।
৩. যদি একটি ফাঁকা স্লট পাওয়া যায়, তবে কাজটিকে সেই স্লটে বরাদ্দ করুন এবং স্লটটিকে 'ব্যবহৃত (used)' হিসেবে চিহ্নিত করুন।
৪. যদি কোনো ফাঁকা স্লট না থাকে, তবে কাজটি এড়িয়ে যান (skip)।

সবচেয়ে সর্বশেষ (latest) উপলব্ধ স্লটে (সবচেয়ে আগেরটির পরিবর্তে) বরাদ্দ করাটা ইচ্ছাকৃতভাবে করা হয় — এর ফলে ভবিষ্যতে এমন অধিক লাভের কাজগুলো (high-profit tasks) সহজে করা যায় যেগুলোর ডেডলাইন হয়তো খুব কাছাকাছি।

ইউনিয়ন-ফাইন্ডের (Union-Find) সাহায্যে দ্রুত স্লট খোঁজা

সাধারণ পদ্ধতি (naive approach): প্রতিটি টাস্কের জন্য, এর শুরুর ডেডলাইন থেকে পেছনের দিকে খুঁজতে থাকুন যতক্ষণ না আপনি একটি ফাঁকা স্লট পাচ্ছেন। এর ফলে প্রতি টাস্কের জন্য O(n) সময় লাগে, এবং মোট সময় লাগে O(n²) — যা অনেক ধীর।

বুদ্ধিদীপ্ত পদ্ধতি (smart approach): একটি ইউনিয়ন-ফাইন্ড বা Union-Find (ডিসজয়েন্ট সেন্ট বা disjoint set) স্ট্রাকচার বজায় রাখুন, যেখানে parent[t] সর্বশেষ ফাঁকা স্লটটি (≤ t) নির্দেশ করে। যখন স্লট t ব্যবহার করা সম্পন্ন হয়, তখন union(t, t−1) করে দিন, যাতে ভবিষ্যতে ≤ t খোঁজার জন্য সিস্টেমটি স্বয়ংক্রিয়ভাবে পরবর্তী ফাঁকা স্লটে চলে যেতে পারে। প্রতিটি খোঁজার কাজের জন্য প্রায়-O(1) অ্যামোরটিজড বা গড় (amortized) সময় লাগে (inverse Ackermann function)। মোট সময়: সর্ট করার জন্য O(n log n), শিডিউলিংয়ের জন্য O(nα(n)) — সর্ট করার ধাপটি সবচেয়ে বেশি সময় নেয়।

গ্রিডি পদ্ধতি কেন সঠিক — ম্যাট্রয়েড তত্ত্ব (Matroid Theory)

একাধিক কাজ যেগুলো নির্দিষ্ট সময়ে সম্পন্ন করা যায় (অর্থাৎ ফিজিবল টাস্ক সেটের কালেকশন) মিলে একটি ম্যাট্রয়েড (matroid) তৈরি করে। যেকোনো ওয়েটেড বা ওজনের ম্যাট্রয়েডের ক্ষেত্রে, গ্রিডি অ্যালগরিদম — ওজনের ক্রমানুসারে বড় থেকে ছোটতে সাজিয়ে, একটি সেট যদি স্বাধীন (independent) থাকে তবে তাতে নতুন কোনো উপাদান যোগ করা — সবচেয়ে বেশি ওজনের স্বাধীন সেট (maximum-weight independent set) খুঁজে বের করে। এখানে গ্রিডি পদ্ধতি কাজ করার পেছনে এটাই হলো গভীর তাত্ত্বিক কারণ: কারণ এর ফিজিবিলিটির (feasibility) ধরন হুবহু ম্যাট্রয়েড ইনডিপেনডেন্সের কাঠামোর মতো।

ফিজিবিলিটির মূল যাচাইকরণ (Key Feasibility Check)

একটি কাজের সেট S তখনই ফিজিবল বা সম্ভব হয় যদি ও কেবল যদি প্রতিটি সময় t এর জন্য, S এ থাকা কাজগুলোর ডেডলাইন ≤ t হয় এবং সেগুলোর সংখ্যা সর্বোচ্চ t হয়। সহজ কথায়: কোনো নির্দিষ্ট ডেডলাইনের মধ্যে যে কয়টি টাইম স্লট আছে, তার চেয়ে বেশি কাজ আপনি করতে পারবেন না। এই শর্তটি ইউনিয়ন-ফাইন্ড ব্যবহার করে বেশ দক্ষতার সাথে যাচাই করা সম্ভব।

দ্রষ্টব্য: সর্বদা একটি কাজকে এর ডেডলাইনের আগের সর্বশেষ উপলব্ধ বা ফাঁকা স্লটে বরাদ্দ করুন — শুরুর দিকের স্লটগুলোতে নয়। এর ফলে শুরুর দিকের স্লটগুলো এমন কাজের জন্য ফাঁকা থাকে যেগুলোর ডেডলাইন অনেক কাছে এবং যেগুলো ক্রমানুসারে সাজানো তালিকায় আপনি পরে পাবেন।

টাস্ক শিডিউলিং — ইউনিয়ন-ফাইন্ডের সাথে গ্রিডি

def task_scheduling(tasks):
    # tasks: list of (profit, deadline)
    tasks.sort(reverse=True)  # sort by profit descending
    if not tasks: return 0, []
    max_deadline = max(d for _, d in tasks)
    # Union-Find: parent[t] = latest free slot <= t
    parent = list(range(max_deadline + 1))
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]  # path compression
            x = parent[x]
        return x
    total = 0
    schedule = []
    for profit, deadline in tasks:
        slot = find(deadline)
        if slot > 0:  # slot 0 is a sentinel (no free slot)
            schedule.append((slot, profit, deadline))
            total += profit
            parent[slot] = slot - 1  # union: next query skips this slot
    schedule.sort()
    return total, schedule


tasks = [(100, 2), (90, 1), (80, 2), (70, 1)]
total, sched = task_scheduling(tasks)
print(f"Max profit: {total}")
for slot, profit, deadline in sched:
    print(f"  Slot {slot}: profit={profit}, deadline={deadline}")
Output
Max profit: 190
  Slot 1: profit=90, deadline=1
  Slot 2: profit=100, deadline=2

Complexity

📊 লাভের (profit) ক্রমানুসারে সাজানো (descending)
সবচেয়ে বেশি সময় নেওয়া অংশ — কারণ গ্রিডি পদ্ধতি লাভের ক্রমানুসারে টাস্কগুলো প্রক্রিয়া করে
একবার সর্ট (sort) করা O(n log n)
🐢 সাধারণ পদ্ধতিতে (Naive) স্লট খোঁজা
প্রতিটি টাস্কের জন্য ডেডলাইন থেকে পেছনের দিকে স্ক্যান করা — যা অনেক ধীর
প্রতিটি টাস্কের স্ক্যান প্রতি টাস্কে O(n) → মোট O(n²)
⚡ ইউনিয়ন-ফাইন্ডের সাথে স্লট খোঁজা
পাথ কম্প্রেশন (path compression) প্রায়-O(1) সময়ে সর্বশেষ ফাঁকা স্লট খুঁজে বের করে
প্রতি কোয়েরিতে প্রায় কনস্ট্যান্ট বা স্থির O(α(n)) অ্যামোরটিজড
🏁 ইউনিয়ন-ফাইন্ডের সাথে মোট সময়
একবার সাজানো + n সংখ্যক প্রায়-O(1) ইউনিয়ন-ফাইন্ড অপারেশন
সাজানোর (Sort) ধাপে সবচেয়ে বেশি সময় লাগে O(n log n)
📦 স্পেস (Space)
সর্বোচ্চ ডেডলাইনের আকারের সমান ইউনিয়ন-ফাইন্ড প্যারেন্ট অ্যারে (parent array)
লিনিয়ার O(n)

ছোট কুইজ

টাস্ক: (লাভ=100, ডেডলাইন=2), (লাভ=90, ডেডলাইন=1), (লাভ=80, ডেডলাইন=2), (লাভ=70, ডেডলাইন=1)। সম্ভাব্য সর্বোচ্চ লাভ কত?

পড়া চালিয়ে যান