$n$ کار با زمان‌های پردازش $t_1,t_2,…,t_n$ به یک کارمند تنبل محول شده‌اند. موعد شروع کار $i$ام $a_i$ و موعد اتمام آن $d_i$ است. کار $i$ام فقط در بازه‌ی $[a_i,d_i]$ قابل انجام است و به محض شروع هر کار باید تا اتمام کار آن را بدون وقفه انجام داد. $a_i$ و$d_i$ و $t_i$ طبیعی هستند و می‌دانیم $d_i-a_i<2t_i$.

اما چون کارمند تنبل است، سعی می‌کند همیشه کم‌ترین زمان ممکن را کار کند. این کارمند رئیسی دارد که مرتبا در هر لحظه او را تحت نظر دارد: اگر ببیند کارمند بیکار است در حالی که کاری قابل اجرا وجود دارد، او را اخراج می‌کند. در لحظه‌ی $t$ به کاری «قابل اجرا» می‌گوییم که از موعد شروع آن $(a_i)$ گذشته باشد و اگر در همین لحظه‌ی $t$ شروع به انجام این کار کنیم، حداکثر تا موعد اتمام آن $(d_i)$ تمام شود.

این کارمند تنبل سعی دارد به نحوی زیرمجموعه‌ای از کارها را انتخاب کند تا اولا اخراج نشود و ثانیا مجموع زمان‌های کارهایی که انجام می‌دهد کمینه شود.

الگوریتمی چند جمله‌ای بر حسب $D$ ($D=max_{i=1…n}d_i$) و $n$ ارائه کنید که این زیرمجموعه از کارها و زمان اجرای هر کدام از کارهای انتخابی را برای کارمند مشخص کند.

• سوال بعد
• سوال قبل