$n$ کار داریم که کار $i$ام در زمان $a_i$ می‌رسد و زمان انجام آن $t_i$ است. کارمند تنبل می‌خواهد تعدادی از این کارها را با رعایت شرایط زیر انجام دهد:

1. کارمند در هر لحظه می‌تواند حداکثر یک کار را انجام دهد.
2. اگر انجام کار $i$ام در زمان $T$ شروع شود تا زمان $T+t_i$ طول می‌کشد.
3. انجام کار $i$ام نباید قبل از زمان $a_i$ شروع شود.
4. هر کاری که کارمند برای انجام دادن انتخاب می‌کند باید حداکثر تا زمان $D$ پایان یابد.
5. هر گاه کاری برای انجام دادن وجود دارد(که اگر شروع شود حداکثر تا زمان $D$ پایان می‌یابد) کارمند نمی‌تواند بی‌کار بماند و باید از میان کارهای موجود یکی را انتخاب کند و انجام دهد.

فرض کنید تمام اعداد صحیح هستند و برای هر $i$ داریم $a_i+t_i\leq D$.

کارمند تنبل است و می‌خواهد زود محل کار خود را ترک کند. اما تنها در صورتی می‌تواند این کار را انجام دهد که کاری برای انجام دادن نداشته باشد و در آینده نیز هیچ کاری قابل انجام دادن نشود.

هدف تعیین ترتیب انجام کارهاست به صورتی که در حداقل زمان ممکن دیگر کاری برای انجام دادن نماند.

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