অ্যাক্টিভিটি সিলেকশন প্রবলেম

১ · সমস্যাটি আনুষ্ঠানিকভাবে

$n$টি অ্যাক্টিভিটি দেওয়া আছে, প্রতিটি অ্যাক্টিভিটি $a_i$-এর একটি শুরুর সময় $s_i$ ও শেষের সময় $f_i$ ($s_i < f_i$)। দুটি অ্যাক্টিভিটি $a_i$ ও $a_j$ সামঞ্জস্যপূর্ণ (compatible) যদি তাদের সময়সীমা ওভারল্যাপ না করে — অর্থাৎ $f_i \le s_j$ অথবা $f_j \le s_i$। লক্ষ্য: সর্বোচ্চ কার্ডিনালিটির (সংখ্যায় সর্বোচ্চ) একটি সাবসেট $S$ বেছে নেওয়া যেখানে $S$-এর প্রতিটি জোড়া পরস্পর সামঞ্জস্যপূর্ণ।

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

২ · গ্রিডি-চয়েস প্রপার্টির প্রমাণ — এক্সচেঞ্জ আর্গুমেন্ট প্রয়োগ

L19-এর টেমপ্লেট অনুযায়ী: অ্যাক্টিভিটিগুলোকে শেষ হওয়ার সময় অনুযায়ী সাজানো আছে ধরে নিই ($f_1 \le f_2 \le \dots \le f_n$)। গ্রিডি প্রথমে $a_1$ (সবচেয়ে আগে শেষ হওয়া) বেছে নেয়। দাবি: কোনো একটি অপটিমাল সমাধান আছে যা $a_1$-কে অন্তর্ভুক্ত করে।

1. ধরে নাও: $A$ একটি অপটিমাল সমাধান, এবং $a_k$ হলো $A$-তে থাকা সবচেয়ে আগে শেষ হওয়া অ্যাক্টিভিটি। যদি $a_k = a_1$ হয়, প্রমাণ শেষ। ধরি $a_k \ne a_1$ (অর্থাৎ $f_k \ge f_1$, কারণ $a_1$-ই সবচেয়ে আগে শেষ হয়)।
2. বদলাও (exchange): $A$ থেকে $a_k$ সরিয়ে তার জায়গায় $a_1$ বসাও — নতুন সেট $A' = (A \setminus \{a_k\}) \cup \{a_1\}$।
3. দেখাও কোনো ক্ষতি হয়নি: যেহেতু $f_1 \le f_k$, তাই $a_1$ যেকোনো অ্যাক্টিভিটির সাথে সামঞ্জস্যপূর্ণ যার সাথে $a_k$ সামঞ্জস্যপূর্ণ ছিল (কারণ $a_1$ আরও আগে শেষ হয়, তাই পরের অ্যাক্টিভিটিগুলোর সাথে সংঘাত কম হওয়ারই কথা)। সুতরাং $A'$-ও একটি বৈধ (সামঞ্জস্যপূর্ণ) সেট, এবং $|A'| = |A|$ — অর্থাৎ $A'$-ও অপটিমাল।
4. ইনডাকশন: এখন $A'$-এ $a_1$ আছে। অবশিষ্ট সমস্যাটি হলো $a_1$-এর পরে শুরু হওয়া অ্যাক্টিভিটিগুলোর মধ্যে থেকে সর্বোচ্চ সাবসেট বেছে নেওয়া — এটি ঠিক একই আকারের একটি ছোট সাবপ্রবলেম, তাই একই যুক্তি পুনরাবৃত্তভাবে প্রয়োগ করা যায়। এভাবেই অপটিমাল সাবস্ট্রাকচার ধরা পড়ে: $a_1$ নেওয়ার পর অবশিষ্ট সমস্যার একটি অপটিমাল সমাধান, $a_1$-এর সাথে যোগ করলে, মূল সমস্যার একটি অপটিমাল সমাধান দেয়।

এই চারটি ধাপ মিলিয়ে প্রমাণ করে যে "সবচেয়ে আগে শেষ হওয়া অ্যাক্টিভিটি বারবার নাও" — এই গ্রিডি স্ট্র্যাটেজি সবসময় সর্বোচ্চ সংখ্যক সামঞ্জস্যপূর্ণ অ্যাক্টিভিটি দেয়। এটি L19-এর কয়েন-চেঞ্জ কাউন্টার-এক্সাম্পল থেকে গুণগতভাবে ভিন্ন — সেখানে ধাপ ৩ ব্যর্থ হয়েছিল, এখানে ধাপ ৩ সফল হয়েছে।

৩ · গ্রিডি বনাম ব্রুট-ফোর্স — একটি প্রকৃত কম্পিউটেশনাল যাচাই

প্রমাণটি রিগোরাস হলেও, আমরা এখানে থামছি না — নিচের কোড সেলে গ্রিডি অ্যালগরিদম এবং একটি সম্পূর্ণ স্বতন্ত্র ব্রুট-ফোর্স এক্সহস্টিভ সার্চ (সব সম্ভাব্য সাবসেট পরীক্ষা করে, প্রথমে সবচেয়ে বড় আকার থেকে শুরু করে) — দুটোই ইমপ্লিমেন্ট করা হয়েছে। ছোট র‍্যান্ডম ইনস্ট্যান্সে ($n \le 9$) বহুবার দুটোর ফলাফলের সংখ্যা তুলনা করা হয়েছে।

import random
from itertools import combinations

def activity_selection_greedy(activities):
    # activities: (start, finish) জোড়ার লিস্ট
    order = sorted(activities, key=lambda a: a[1])   # finish time অনুযায়ী সাজানো
    selected = []
    last_finish = float("-inf")
    for s, f in order:
        if s >= last_finish:      # আগের নেওয়া অ্যাক্টিভিটির সাথে সংঘাত নেই
            selected.append((s, f))
            last_finish = f
    return selected

def is_mutually_compatible(subset):
    # সাবসেটের প্রতিটি জোড়া পরস্পর ওভারল্যাপবিহীন কি না, তা সরাসরি চেক করা
    subset = sorted(subset, key=lambda a: a[0])
    for i in range(1, len(subset)):
        if subset[i][0] < subset[i - 1][1]:
            return False
    return True

def brute_force_max_activities(activities):
    # সত্যিকারের এক্সহস্টিভ সার্চ: সবচেয়ে বড় আকার r = n থেকে নিচের দিকে, প্রতিটি আকারে
    # সব কম্বিনেশন পরীক্ষা করে প্রথম বৈধ (সামঞ্জস্যপূর্ণ) সাবসেট পাওয়ামাত্র থামা
    n = len(activities)
    for r in range(n, 0, -1):
        for combo in combinations(activities, r):
            if is_mutually_compatible(combo):
                return r
    return 0

random.seed(7)
mismatches = 0
trials = 40
for trial in range(trials):
    n = random.randint(1, 9)
    activities = []
    for _ in range(n):
        s = random.randint(0, 15)
        dur = random.randint(1, 6)
        activities.append((s, s + dur))

    greedy_sel = activity_selection_greedy(activities)
    assert is_mutually_compatible(greedy_sel), f"গ্রিডির ফলাফলই সামঞ্জস্যপূর্ণ নয়: {activities}"
    greedy_count = len(greedy_sel)
    brute_count = brute_force_max_activities(activities)

    if greedy_count != brute_count:
        mismatches += 1
        print(f"MISMATCH: {activities} -> greedy={greedy_count}, brute={brute_count}")

print(f"মোট ট্রায়াল: {trials}, গ্রিডি ও ব্রুট-ফোর্সের মধ্যে অমিল: {mismatches}")

# একটি নির্দিষ্ট উদাহরণ দেখানো
example = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9), (6, 10), (8, 11), (8, 12), (2, 14), (12, 16)]
print("\nউদাহরণ ইনপুট:", example)
print("গ্রিডি সিলেকশন:", activity_selection_greedy(example))
print("গ্রিডি সংখ্যা vs ব্রুট-ফোর্স সংখ্যা:",
      len(activity_selection_greedy(example)), "vs", brute_force_max_activities(example))