حل تشریحی سوال شماره 47 دروس مشترک

فرض کنید n کار در اختیار داریم. زمان شروع و خاتمه کار i ام به‌ترتیب $s_i$ و $f_i$ است. یک پردازنده در اختیار داریم. می‌خواهیم بیشترین تعداد کاری که می‌توان به وسیله این پردازنده اجرا کرد را محاسبه کنیم. طبیعی است دو کاری که اشتراک زمانی داشته باشند نمی‌توانند بوسیله یک پردازنده همزمان اجرا شوند. برای حل این مسئله الگوریتم حریصانه متعارف بدین شکل است. کارها براساس یک پارامتر به‌صورت صعودی مرتب می‌شوند. براساس ترتیب فوق، کارها پردازش شده و اگر هر کار با کارهای قبلی که در خروجی قرار گرفته، هم‌پوشانی زمانی نداشته باشد در خروجی قرار می‌گیرد. به ازای چه تعداد از پارامترهای زیر الگوریتم فوق درست کار می‌کند؟

$s_i+f_i$

$f_i$

$s_i$

$f_i{s}_i$