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

ইন্টারভাল শিডিউলিং (Interval Scheduling)

সর্বোচ্চ সংখ্যক মিটিং সিডিউল করুন — সবসময় সেই মিটিংটি আগে বেছে নিন যা সবচেয়ে আগে শেষ হয়
time:দ্রুত · \(O(n \log n)\)space:খুবই কম · \(O(1)\)key insight:শুরু হওয়ার সময়ের বদলে শেষ হওয়ার সময় অনুযায়ী সাজান

কল্পনা করুন আপনি একটি অফিসের ম্যানেজার এবং আপনার একটি মাত্র কনফারেন্স রুম আছে। কর্মীরা সারা দিন বিভিন্ন মিটিংয়ের জন্য অনুরোধ পাঠাচ্ছেন, যার প্রতিটিতে শুরু এবং শেষ হওয়ার সময় দেওয়া আছে। আপনি চান সারা দিনে ওই রুমে যেন সর্বোচ্চ সংখ্যক মিটিং আয়োজন করা যায় — শর্ত শুধু একটিই, একটি মিটিং চলাকালীন অন্যটি শুরু হতে পারবে না (ওভারল্যাপ)।

আপনি কোন মিটিংগুলো আগে বেছে নেবেন? এখানে একটি মজার এবং কার্যকর বুদ্ধি হলো: সবসময় সেই মিটিংটি আগে বেছে নিন যা সবার আগে শেষ হয়। কোনটি সবচেয়ে ছোট বা কোনটি সবার আগে শুরু হবে সেটি বড় কথা নয়; যা সবার আগে শেষ হবে সেটিই আসল।

গ্রিডি বা লোভী পদ্ধতি (The Greedy Algorithm)

১. সব মিটিংকে তাদের শেষ হওয়ার সময় (ascending order) অনুযায়ী সাজান।
২. তালিকার প্রথম মিটিংটি বেছে নিন এবং এর শেষ হওয়ার সময়টিকে 'সর্বশেষ ব্যবহৃত সময়' হিসেবে চিহ্নিত করুন।
৩. তালিকার বাকি মিটিংগুলো চেক করুন: যদি কোনো মিটিং আগের মিটিংয়ের শেষ হওয়ার সময় বা তার পরে শুরু হয়, তবে সেটি গ্রহণ করুন এবং সর্বশেষ শেষ হওয়ার সময়টি আপডেট করুন।
৪. যদি কোনো মিটিং বর্তমানের সর্বশেষ শেষ হওয়ার সময়ের আগে শুরু হয়, তবে সেটি বাদ দিন (কারণ এটি আগেরটির সাথে ওভারল্যাপ করবে)।

ব্যাস, এটুকুই! একবার সর্টিং এবং একবার লিনিয়ার স্ক্যান = সর্বমোট \(O(n \log n)\) সময়।

শুরু হওয়ার সময় বা ব্যাপ্তি অনুযায়ী কেন সাজাবেন না?

শুরু হওয়ার সময় অনুযায়ী: একটি মিটিং হয়তো সকাল ৯টায় শুরু হলো কিন্তু চলল সন্ধ্যা ৬টা পর্যন্ত। এটি নিলে আপনার পুরো দিনটাই অন্য সব মিটিংয়ের জন্য বন্ধ হয়ে যাবে। আগে শুরু হওয়া মানেই অন্যদের জন্য সময় ছেড়ে দেওয়া নয়।

ব্যাপ্তি (duration) অনুযায়ী: একটি ৩০ মিনিটের মিটিং হয়তো অন্য ১০টি মিটিংয়ের মাঝখানে এমনভাবে বাধা হয়ে দাঁড়াতে পারে যে আপনি একটি নিতে গিয়ে ১০টি হারালেন। আবার একটি ১ ঘণ্টার মিটিং হয়তো অন্য কারো সাথে মোটেও সংঘাত তৈরি করছে না। ছোট হওয়া মানেই যে এটি অন্য সবার জন্য সুবিধাজনক হবে তা নয়।

শেষ হওয়ার সময় অনুযায়ী: এটিই হলো সঠিক প্যারামিটার। যে মিটিংটি দ্রুত শেষ হবে সেটি পরবর্তী মিটিংগুলোর জন্য সবচেয়ে বেশি সময় ফাঁকা রাখবে। 'এক্সচেঞ্জ আর্গুমেন্ট' এর মাধ্যমে এটি গাণিতিকভাবেও প্রমাণ করা যায়।

এক্সচেঞ্জ আর্গুমেন্ট (Exchange Argument) এর মাধ্যমে প্রমাণ

ধরুন সব সেরা সিডিউলের একটি সেট হলো OPT যা আপনার গ্রিডি সিদ্ধান্তের (সবচেয়ে আগে শেষ হওয়া মিটিং G) চেয়ে আলাদা একটি মিটিং A দিয়ে শুরু করেছে। যেহেতু G মিটিংটি A-র আগে শেষ হয় অথবা একই সময়ে শেষ হয়, তাই আমরা OPT-তে A-র বদলে G বসাতে পারি। G বসালে পরবর্তী কোনো মিটিংয়ের ওপর কোনো নেতিবাচক প্রভাব পড়বে না কারণ এটি A-র চেয়ে অন্তত আগে শেষ হচ্ছে। এভাবে প্রতিটি পদক্ষেপে আমরা দেখাতে পারি যে গ্রিডি পদ্ধতিই সেরা উত্তর দিতে সক্ষম।

ইন্টারভাল পার্টিশনিং (Interval Partitioning)

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

ওয়েটেড ইন্টারভাল শিডিউলিং (যখন গ্রিডি ব্যর্থ হয়)

যদি মিটিংগুলোতে আলাদা আলাদা 'প্রফিট' বা গুরুত্ব থাকে এবং আপনার লক্ষ্য হয় সংখ্যার বদলে মোট 'প্রফিট' বাড়ানো, তবে গ্রিডি বা লোভী পদ্ধতি কাজ করবে না। একটি লাভজনক ৮ ঘণ্টার মিটিং হয়তো চারটি ১ ঘণ্টার কম গুরুত্বপূর্ণ মিটিংয়ের চেয়ে বেশি মূল্যবান হতে পারে। এই সমস্যা সমাধানের জন্য ডায়নামিক প্রোগ্রামিং (DP) প্রয়োজন হয়।

Click chart to zoom
গ্রিডি ইন্টারভাল শিডিউলিং: শেষ হওয়ার সময় অনুযায়ী সাজিয়ে ওভারল্যাপ ছাড়া মিটিং গ্রহণ করা
দ্রষ্টব্য: সবচেয়ে আগে শেষ হওয়ার সময়টাই হলো জাদুকরী সর্টিং কি (sort key)। এভাবে ভাবুন: যে আগে পথ ছেড়ে দেবে বা কনফারেন্স রুমটি ফাঁকা করে দেবে, সে অন্যদের কাজ শুরুর সুযোগ করে দিচ্ছে। তাই আগে শুরু করার চেয়ে আগে শেষ করার গুরুত্ব এখানে অনেক বেশি।

ইন্টারভাল শিডিউলিং — সর্বোচ্চ বিরতিহীন মিটিং

def max_meetings(intervals):
    # Sort by end time
    intervals.sort(key=lambda x: x[1])
    count = 0
    last_end = -1
    selected = []
    for start, end in intervals:
        if start >= last_end:
            selected.append((start, end))
            last_end = end
            count += 1
    return count, selected


# List of meetings (start, end)
meetings = [(1,4),(3,5),(0,6),(5,7),(3,9),(5,9),(6,10),(8,11),(8,12),(2,14),(12,16)]
n, chosen = max_meetings(meetings)
print(f"Max meetings: {n}")
for s, e in chosen:
    print(f"  [{s}, {e})")
Output
Total max meetings: 4
  [1, 4)
  [5, 7)
  [8, 11)
  [12, 16)

Complexity

🗂️ শেষ হওয়ার সময় অনুযায়ী সর্ট
এটিই প্রধান ধাপ — এরপরের কাজগুলো সম্পূর্ণ লিনিয়ার
একবার সর্ট করা \(O(n \log n)\)
➡️ গ্রিডি স্ক্যান
প্রতিটি মিটিং একবার করে চেক করা; হয় নেওয়া হবে নাহলে বাদ
মাত্র একটি স্ক্যান \(O(n)\)
📦 স্পেস বা মেমোরি
শুধুমাত্র সর্বশেষ সিলেক্ট করা মিটিংয়ের শেষ সময়টি মনে রাখতে হয়
খুবই সামান্য \(O(1)\)
🏢 ইন্টারভাল পার্টিশনিং (রুম সংখ্যা)
প্রায়োরিটি কিউ ব্যবহার করে ট্র্যাক করা হয় কোন রুমটি কখন ফাঁকা হচ্ছে
সর্ট + মিন-হিপ \(O(n \log n)\)
💰 ওয়েটেড ভ্যারিয়েন্ট (প্রফিট বাড়ানো)
এক্ষেত্রে গ্রিডি পদ্ধতি কাজ করে না; ডিপি ব্যবহার করা প্রয়োজন
ডিপি + বাইনারি সার্চ \(O(n \log n)\)

ছোট কুইজ

আপনার কাছে ৪টি মিটিং আছে: [১,১০], [২,৩], [৪,৫], [৬,৭]। গ্রিডি পদ্ধতিতে (শেষ হওয়ার সময় অনুযায়ী) কোন কোনটি সিলেক্ট হবে?

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

গ্রিডি প্যাটার্ন বা লোভী পদ্ধতি (Greedy Pattern)
দাওয়াতের মাংসের সবচেয়ে বড় টুকরোটি সবসময় তুলে নিন — কখনো এটি সেরা সমাধান দেয়, আবার কখনো দেয় না
→
টাস্ক শিডিউলিং (Task Scheduling)
কাছের ডেডলাইন অনুযায়ী আগে কাজ করুন — কোনো কাজ মিস হবে না, সবচেয়ে বেশি লাভ হবে
→
ইন্টারভালের উপর ডিপি (DP on Intervals)
প্রথমে ছোট ছোট অংশগুলোকে সমাধান করুন, তারপর সেগুলোকে বড় অংশে একত্রিত করে ফেলুন বা মার্জ (merge) করুন
→