‎$n$‎ بازه‌ی ‎$[a_i,b_i]$‎ به ما یک به یک داده می‌شوند که ‎$a_i$‎ و ‎$b_i$‎ اعدادی طبیعی هستند. یک محور از اعداد طبیعی هم در نظر بگیرید. در ابتدا کل محور سفید است. با گرفتن هر بازه تمام قسمتی که توسط آن پوشیده می‌شود را سیاه می‌کنیم. می‌خواهیم پس از گرفتن هر بازه و قبل از دریافت بازه‌ی بعد، بزرگترین مقدار ‎$x$‎ را مشخص کنیم طوری که ‎$[1,x]$‎ سیاه است. الگوریتمی از مرتبه‌ی ‎${ \cal O}(n \lg n)$‎ ارائه کنید.

• سوال قبل