====== کارمند تنبل ======



$n$ کار داریم که کار $i$ام در زمان $a_i$ می‌رسد و زمان انجام آن $t_i$ است. کارمند تنبل می‌خواهد تعدادی از این کارها را با رعایت شرایط زیر انجام دهد:
  - کارمند در هر لحظه می‌تواند حداکثر یک کار را انجام دهد.
  - اگر انجام کار $i$ام در زمان $T$ شروع شود تا زمان $T+t_i$ طول می‌کشد.
  - انجام کار $i$ام نباید قبل از زمان $a_i$ شروع شود.
  - هر کاری که کارمند برای انجام دادن انتخاب می‌کند باید حداکثر تا زمان $D$ پایان یابد.
  - هر گاه کاری برای انجام دادن وجود دارد(که اگر شروع شود حداکثر تا زمان $D$ پایان می‌یابد) کارمند نمی‌تواند بی‌کار بماند و باید از میان کارهای موجود یکی را انتخاب کند و انجام دهد.


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

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

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


<پاسخ>



</پاسخ>


  * [[سوال ۳|سوال بعد]]
  * [[سوال ۱|سوال قبل]]