====== مسئله‌ی زمانبندی پردازه‌ها ======



===== تعریف =====


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

(در [[زمانبندی_پردازه‌های_وزن‌دار|حالت کلی تر مسئله]] هر پردازه یک مقدار سود تولید می‌کند و می‌خواهیم سود بیشینه شود)

===== الگوریتم =====

فرض کنید $S_{ij}$ مجموعه پردازه هایی باشد که بین دو پردازه‌ی $a_j$ , $a_i$ هستند و تداخلی با آن دو ندارند و $A_{ij}$  جواب بهینه‌ی این مجموعه‌ی پردازه‌ها باشد. از آنجا که این مسئله دارای [[الگوریتم‌های_حریصانه|زیر ساختار بهینه]] است، در صورتی که $a_k$ درون یک جواب بهینه باشد، رابطه‌ی $ A_{ij} = A_{ik} + A_{kj} + 1$ برقرار است .

فرض کنید $a_i$ ها به ترتیبی باشند که $f_1 \lt f_2 \lt f_3 ... \lt f_n $ ، در این صورت با اضافه کردن $a_1$ به یک جواب بهینه‌ی دلخواه ، $a_1$ حد اکثر با یک بازه‌ی دیگر  تداخل پیدا می‌کند ، زیرا تمام بازه هایی که با $a_1$ تداخل دارند از نقطه‌ی $f_1$ می‌گذرند. با حذف بازه‌ای که با $a_1$ تداخل دارد به یک جواب بهینه‌ی دیگر می‌رسیم، که نشان می‌دهد همواره جواب بهینه‌ای وجود دارد که شامل بازه‌ی اول باشد، پس $a_1$ انتخاب حریصانه‌ی مناسبی است.

درنتیجه الگوریتم حریصانه‌ی زیر جواب بهینه را می‌دهد:
در هر مرحله بازه ای با کوچک ترین $f_i$ را که با مجوعه جواب تداخل ندارد را به جواب اضافه می‌کنیم. جواب حاصل تعداد بازه‌های بیشینه را می‌دهد. 
===== پیچیدگی‌ الگوریتم =====
در صورت مرتب بودن بازه‌ها به ترتیب انتهای بازه ، پیچیدگی الگوریتم از $O(n)$ است وگر نه به دلیل مرتب سازی پیچیدگی از $O(nlgn)$ می‌شود.


===== پیاده‌سازی اولیه =====

<code c A.c>
for(int i = 0 ; i < n ; ++i){
   bool canBeSelected=true;
   for(int j = 0 ; j < i ; ++j)
      if(selected[j] && hasConflict(i,j)){                 // اگر دو بازه تداخل داشته باشند و جی در مجموعه جواب باشد
          canBeSelected=false;
          break;
      }
   if(canBeSelected){
       selected[i]=true;
       ans.push_back(i);
   }
} 
</code>

===== پیاده‌سازی سریع‌تر =====
بازه ها دراین کد به صورت $[s_i,f_i)$ فرض شده‌اند.

از آنجا که $f_i$ ها مرتب شده هستند. تنها کافیست تداخل را با آخرین بازه چک کنیم.
<code c ‌‌B.c>
int lastEnd=-inf;
for(int i = 0 ; i < n ; ++i){
   bool canBeSelected=true;
   if(s[i] < lastEnd)
       canBeSelected=false;   
   if(canBeSelected){
       selected[i]=true;
       lastEnd=f[i];     
       ans.push_back(i);
   }
} 
</code>


===== کابردها =====


**مثال**:
صورت مسئله اینجا می‌آید.

<پاسخ>

پاسخ مسئله اینجا می‌آید

</پاسخ>


===== مسائل نمونه =====


  * [[سوالات_المپیاد:دوره‌ی_تابستان:دوره‌ی_۲۴:عملی_مقدماتی_اول:سوال_۱|سوال عملی دوره‌ی تابستان ۲۴]] [سطح: ساده]
===== مراجع =====

  * [[http://e-maxx.ru/algo/euler_function|تابع اویلر - سایت ماکزیمال]]
  * [[http://en.wikipedia.org/wiki/Euler%27s_totient_function|تابع اویلر - ویکی‌پدیا]]