حل تشریحی سوال شماره 12 طراحی الگوریتم

می‌دانیم ترتیب شروع و پایان فعالیت‌های H و G و F و E و D و C و B و A از چپ به راست به‌صورت $a_s{b}_s{c}_s{a}_e{d}_s{c}_e{e}_s{f}_s{b}_e{d}_e{g}_s{e}_e{f}_e{h}_s{g}_e{h}_e$ است. در اینجا $x_s$ زمان شروع و $x_e$ زمان پایان فعالیت X می‌باشد. می‌خواهیم این فعالیت‌ها را در تعدادی اتاق که در اختیار داریم انجام دهیم. یک فعالیت در یک اتاق قابل انجام است، اگر در تمام مدت آن فعالیت اتاق به‌طور کامل در اختیارش باشد. حداقل تعداد اتاق‌های مورد نیاز برای انجام همه فعالیت‌ها کدام است؟