الگوریتم حریصانه
کاربردها > مسئلهٔ برنامه‌ریزی چندین فعالیت همزمان:

مسئلهٔ برنامه‌ریزی چندین فعالیت که همزمان انجام می‌پذیرند نیاز به استفادهٔ همزمان از یک منبع مشترک با هدف انتخاب مجموعه‌ای با ماکزیمم اندازه از فعالیت‌هایی که با هم هم‌پوشانی ندارند، دارند.
فرض کنید یک مجموعهٔ {s = {a1, a2, …, an از n فعالیت پیشنهادی داریم که می‌خواهند از یک منبع استفاده نمایند، مانند یک تالار سخنرانی که در یک زمان می‌تواند تنها مورد استفادهٔ یک فعالیت قرار گیرد. هر فعالیت ai دارای زمان شروع si و زمان خاتمهٔ fi است به‌طوری‌که ۰ ≤ fi> si <∞. اگر فعالیت ai انتخاب شود، می‌تواند در طول بازهٔ (si, fi] رخ دهد.
تعریف: دو فعالیتی را سازگار می‌گوییم که با یکدیگر هم‌پوشانی نداشته باشند.
مسئله انتخاب فعالیت عبارت است از انتخاب یک زیرمجموعه با ماکزیمم اندازه از فعالیت‌هایی که هم‌پوشانی ندارند. برای مثال زیرمجموعهٔ s از فعالیت‌ها را در نظر بگیرید که آن‌ها را برحسب زمان پایان به ترتیب صعودی یکنواخت مرتب کرده‌ایم:
i -> 1 2 3 4 5 6 7 8 9 10 11
  si -> 1 3 0 5 3 5 6 8 8 2 12
  fi -> 4 5 6 7 8 9 10 11 12 13 14
برای این مثال زیرمجموعهٔ {a3, a9, a11} شامل فعالیت‌هایی است که هم‌پوشانی ندارند.
اگرچه این زیرمجموعه بیشینه نیست، چون زیرمجموعهٔ {a1, a4, a9, a11} بزرگ‌تر از آن است. در حقیقت {a1, a4, a9, a11} بزرگ‌ترین زیرمجموعه از فعالیت‌های متقابلاً سازگار است.
حال یک الگوریتم حریصانه بازگشتی برای حل مسئلهٔ زمان‌بندی فعالیت‌ها ارائه خواهیم نمود.
با تعریف مجموعهٔ {sij = {ak € s: fi ≤ sk <fk ≤ sj شروع می‌کنیم، به‌طوری‌که sij زیرمجموعه‌ای از فعالیت‌ها در S است که می‌توانند بعد از خاتمه فعالیت ai شروع شده و قبل از شروع فعالیت aj خاتمه یابند. در حقیقت sij شامل همه فعالیت‌هایی است که با ai و aj و همچنین با همه فعالیت‌هایی که بعد از خاتمه ai خاتمه نیافته و همه فعالیت‌هایی که قبل از شروع aj شروع نمی‌شوند، سازگارند. به منظور بیان کل مسئله، فعالیت‌های ساختگی a0 و an+1 را اضافه کرده و توافق می‌کنیم که f0 = ۰ و ∞ = sn+1 پس s = s0, n+1 و محدودهٔ تغییر i و j به صورت زیر خواهد بود:
0 ≤ i, j ≤ n+1
دامنهٔ تغییر i و j را به صورت زیر می‌توانیم بیشتر محدود کنیم. فرض می‌کنیم که فعالیت‌ها در یک ترتیب یکنواخت صعودی از زمان‌های خاتمه مرتب شده‌اند:
f0 ≤ f1 ≤ f2 ≤ … ≤ fn ≤ fn+1
ادعا می‌کنیم که sij = ᴓ هر گاه i ≥ j باشد. فرض کنید یک فعالیت ak € sij برای i ≥ j وجود دارد به‌طوری‌که ai بعد از aj در ترتیب مرتب قرار دارد. پس خواهیم داشت fi ≤ sk <fk ≤ sj <fj.
بنابراین fi <fj که با این فرض که ai بعد از aj در ترتیب مرتب قرار دارد در تناقض است. می‌توانیم نتیجه بگیریم با این فرض که فعالیت‌ها را در یک ترتیب صعودی یکنواخت از زمان‌های خاتمه مرتب کرده‌ایم، فضای زیر مسائل انتخاب زیر مجموعه با ماکزیمم اندازه شامل فعالیت‌های متقابلاً سازگاراز sij است، که با آگاهی از این مطلب که تمام sijهای دیگر تهی هستند رابطه زیر برقرار است:
0 ≤ i, j ≤ n+1
برای مشاهدهٔ زیرساختار مسئلهٔ انتخاب فعالیت، تعدادی زیرمسئله غیر تهی sij را در نظر بگیرید؛ و فرض کنید که یک جواب برای sij شامل تعدادی فعالیت ak است. به‌طوری‌که fi ≤ sk <fk ≤ sj. استفاده از فعالیت ak سبب ایجاد دو زیرمسئله می‌شود، sik (فعالیت‌هایی که پس از خاتمهٔ فعالیت ai شروع شده و قبل از شروع فعالیت ak خاتمه می‌یابند) و skj (فعالیت‌هایی که پس از خاتمهٔ ak شروع شده و قبل از شروع فعالیت aj خاتمه می‌یابند)، که هر کدام از یک زیرمجموعه شامل فعالیت‌های داخل sij تشکیل شده‌اند. جواب sij اجتماع جواب‌های مربوط به sik و skj است، همراه با فعالیت ak. بنابراین تعداد فعالیت‌ها در جواب sij برابر اندازه جواب skj به علاوه یک (برای ak) می‌باشد.
اکنون فرض کنید جواب Aij برای sij شامل فعالیت ak می‌باشد. پس جواب‌های Aik برای sik و Akj برای skj که در این جواب بهینه برای sij استفاده می‌شوند نیز باید بهینه باشند. بحث برش – و – الصاق معمول در این مورد بکار می‌رود. اگر یک جواب Áik برای sik می‌داشتیم که شامل فعالیت‌های بیشتری از Aik می‌بود، می‌توانستیم Aik را از داخل Aij برش داده و به داخل Áik الصاق نماییم، بنابراین یک جواب دیگر برای sij با تعداد فعالیت‌های بیشتری از Aij تولید می‌شود. از آنجا که فرض کردیم Aij یک جواب بهینه است، به یک تناقض رسیده‌ایم. به‌طور مشابه اگر جواب Ákj برای skj را با فعالیت‌های بیشتر از Akj می‌داشتیم، می‌توانستیم Akj را با Ákj جایگزین کنیم تا یک جواب با فعالیت‌های بیشتری از Aij تولید نماییم.
اکنون از زیرساختار بهینه خود استفاده می‌کنیم تا نشان دهیم که می‌توانیم یک جواب بهینه برای مسئله از روی جواب‌های بهینهٔ زیرمسائل بسازیم. مشاهده کردم که هر جواب برای یک زیرمسئلهٔ غیرتهی sij شامل فعالیت ak است و آن که هر جواب بهینه در درون خود شامل جواب‌های بهینهٔ نمونه زیرمسئله‌های sik و skj می‌باشد؛ بنابراین، می‌توانیم یک زیرمجموعه با ماکزیمم اندازه از فعالیت‌های متقابلاً سازگار در sij بسازیم. با تقسیم مسئله به دو زیرمسئله (یافتن زیرمجموعه‌های با ماکزیمم اندازه از فعالیت‌های متقابلاً سازگار در sik و skj) و پیدا کردن زیرمجموعه‌های با ماکزیمم اندازه Aik و Akj از فعالیت‌های متقابلاً سازگار برای این زیرمسائل و سپس تشکیل زیرمجموعه Aij با ماکزیمم اندازه شامل فعالیت‌های متقابلاً سازگار به صورت
Aik υ {ak} υ Akj = Aij
یک جواب بهینه برای کل مسئله و یک جواب برای s0, n+1 است.