همان داستان مسئله‌ی قبل را درنظر بگیرید. دولت پس از این‌که فهمید نرخ‌های کاذب به گوش برخی از اهالی رسیده، بسیار ناراحت شد و تصمیم گرفت بی‌خیال آلودگی صوتی شده و تنها از طریق همان جارزدن اقدام به اطلاع رسانی کند. در همین راستا، هیچ‌کس هم حق ندارند خبر را به نفر دیگری انتقال بدهند و هر یک از اهالی تنها خبری را باید بپذیرد که از دهان جارچی می‌شنود. این بار خبر این است: ‎«سهمیه بنزین ‎۶۰۰‎ لیتر شده است».

برای این منظور، دولت می‌خواهد با دانستن ‎«محدوده‌ی روی بالکن بودن»‎ هر یک از اهالی، به جارچی دستور بدهد تا با کم‌ترین تعداد جار ‎($k$)‎ در زمان‌های بهینه‌ی ‎$t_2$‎، ‎$t_1$‎ تا ‎$t_k$‎ خبر ثابت ماندن سهمیه را در میدان شهر اعلام کند.

به دولت و جارچی کمک کنید و الگوریتمی از ‎${\cal O}(n\lg n)$‎ ارائه کنید تا با دانستن زمانی که هر یک از افراد روی بالکن هستند کم‌ترین تعداد دفعه‌ی لازم برای جار زدن ‎($k$)‎ و زمان جارها(‎$t_i$‎‎ها) را طوری معین کند که هر یک از اهالی حداقل در یکی از این زمان‌ها روی بالکن خانه‌اش باشد. درستی الگوریتم خود را اثبات کنید. ‎

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