$n$ بازه با مختصات روی محور اعداد $1...m$ داده شده است. می‌خواهیم حداقل تعداد بازه را انتخاب کنیم به‌طوری که هر نقطه با مختصات صحیح روی این محور حداقل در $k$ بازه آمده باشد. ($1\leq k \leq n$)

برای حل این مسئله الگوریتمی از $O(n\quad log\quad m\quad log\quad n)$ ارائه دهید و درستی آن‌را اثبات کنید.

راهنمایی: مقایسه‌ی دو عدد صحیح بین ۱ و $m$ از $\Theta(n\quad log\quad m)$ است.

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