Greedy algorithm: interval scheduling ও greedy কখন ব্যর্থ

Greedy algorithm এখনকার সেরা মনে হওয়া পছন্দ নিয়ে উত্তর গড়ে এবং আর ফিরে তাকায় না। সাধারণত ছোট ও দ্রুত, প্রায়ই একটি sort-এর পর। ফাঁদটি হলো: সমস্যার গঠন ঠিক থাকলেই এটি সঠিক। interview-তে greedy প্রশ্ন প্রিয় কারণ code সহজ আর কঠিন অংশ হলো প্রমাণ। নিচের code ও output প্রকাশের আগে Python 3-এ চালানো।

উদাহরণ ১: interval scheduling (greedy কাজ করে)

আপনার কাছে শুরু ও শেষের সময়সহ কয়েকটি meeting এবং একটি ঘর। কোনো overlap ছাড়া সবচেয়ে বেশি কয়টি meeting-এ থাকা যায়?

যে greedy নিয়ম কাজ করে: শেষের সময় ধরে sort করুন এবং যেগুলো ঢোকে তাদের মধ্যে যেটি আগে শেষ হয় সেটি নিন। আগে শেষ হলে বাকিদের জন্য বেশি জায়গা থাকে। শুরুর সময় বা ছোট দৈর্ঘ্য ধরে sort লোভনীয় কিন্তু ভুল।

উদাহরণ ২: coin change (greedy ব্যর্থ)

"যে সবচেয়ে বড় coin ঢোকে সেটি নিন" [25, 10, 5, 1]-এ কাজ করে, কিন্তু [4, 3, 1] ও পরিমাণ 6-এ নয়। greedy নেয় 4 + 1 + 1 = তিনটি coin, অথচ 3 + 3 = দুটি coin ভালো। greedy ভুল হলে dynamic programming লাগে।

উদাহরণ ৩: jump game

প্রতিটি index থেকে কত দূর লাফ দেওয়া যায় তা দেওয়া আছে। শেষ index-এ পৌঁছানো যাবে কি? এখন পর্যন্ত পৌঁছানো সবচেয়ে দূরের index ধরে রাখুন। তার চেয়ে দূরের কোনো index-এ নামলে আটকে গেলেন।

Code

def max_activities(intervals):
    """Most non-overlapping intervals: sort by end time, take whatever fits."""
    chosen, last_end = [], float("-inf")
    for start, end in sorted(intervals, key=lambda x: x[1]):
        if start >= last_end:
            chosen.append((start, end))
            last_end = end
    return chosen

def greedy_coins(coins, amount):
    count = 0
    for c in sorted(coins, reverse=True):
        count += amount // c
        amount %= c
    return count if amount == 0 else None

def best_coins(coins, amount):          # dynamic programming, for comparison
    INF = float("inf")
    dp = [0] + [INF] * amount
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a and dp[a - c] + 1 < dp[a]:
                dp[a] = dp[a - c] + 1
    return dp[amount] if dp[amount] != INF else None

def can_jump(nums):                      # can you reach the last index?
    reach = 0
    for i, step in enumerate(nums):
        if i > reach:
            return False
        reach = max(reach, i + step)
    return True

আসল output

activities: [(1, 4), (5, 7), (8, 11), (12, 16)]
coins [25,10,5,1], 63: greedy 6 best 6
coins [4,3,1], 6: greedy 3 best 2
jump [2,3,1,1,4]: True | [3,2,1,0,4]: False
activity selection matches brute force on 500 random cases

এখানে greedy চারটি meeting পেয়েছে: (1, 4), (5, 7), (8, 11) ও (12, 16)। interval-scheduling function-কে 500টি random ক্ষেত্রে সব উপসেটের brute-force যাচাইয়ের সঙ্গে মিলিয়ে দেখা হয়েছে, দুটি সবসময় একমত। coin উদাহরণ ব্যর্থতা দেখায়: 6-এর জন্য greedy ৩টি coin নিয়েছে যেখানে সেরা ২টি, তাই DP সংস্করণ দরকার।

greedy নিরাপদ কি না বুঝবেন যেভাবে

1. Greedy-choice property। কোনো সর্বোত্তম উত্তর আপনার greedy পছন্দ দিয়ে শুরু হয়, এটি যুক্তি দিয়ে দেখাতে পারেন?
2. Exchange argument। যেকোনো সর্বোত্তম উত্তরে আপনার greedy পছন্দ বসান। তাতে কখনও খারাপ না হলে greedy নিরাপদ।
3. brute force-এর সঙ্গে test করুন ছোট random input-এ, উপরের মতো। একটি counterexample পেলে greedy বাদ দিন।

সাধারণ ভুল

• প্রমাণ বা counterexample খোঁজা ছাড়া যুক্তিসঙ্গত মনে হওয়া নিয়ম বেছে নেওয়া।
• ভুল key-তে sort করা, যেমন scheduling-এ শেষের সময়ের জায়গায় শুরুর সময়।
• যেকোনো coin-এর মানে coin change-এ greedy ব্যবহার।
• "উদাহরণে পাস করেছে" কে প্রমাণ ভাবা।
• sort-এর খরচ ভুলে যাওয়া: O(n log n)।

মূল কথা: greedy স্থানীয়ভাবে সেরা বিকল্প নেয় এবং কেবল তখনই সঠিক যখন তা ন্যায্যতা দেখানো যায়। সঠিক key-তে sort করুন, brute force-এর সঙ্গে test করুন, আর counterexample পেলে dynamic programming-এ ফিরুন।

---

Interview প্রস্তুতি ও DSA সিরিজ, পর্ব ৩ (আরও algorithm): 4 নম্বর (মোট 5)। আগের লেখা: Trie (prefix tree): autocomplete ও prefix search.