«هپید»‎ در جشن تولد خود ‎$n$‎ تا ‎«بازه»‎ هدیه گرفته است‎!‎ نقطه‌ی شروع هر بازه، ‎$a_i$‎ و نقطه پایان آن ‎$b_i$ ($a_i < b_i$)‎ است. هپید می‌داند که هیچ ‎$i$‎ و ‎$j$‎ متفاوتی وجود ندارند به طوری که ‎$a_i \leq a_j$‎ و ‎$b_i \geq b_j$‎ .

او می‌خواهد این ‎$n$‎ بازه را با ‎$x$‎ رنگ، رنگ‌آمیزی کند به طوری که هیچ سه بازه متفاوت ‎$i$‎ و ‎$j$‎ و ‎$k$‎ وجود نداشته باشند که

هر سه‌شان هم‌رنگ باشند، و بازه ‎$i$‎ با بازه ‎$j$‎ اشتراک داشته باشد، بازه ‎$j$‎ با بازه ‎$k$‎ اشتراک داشته باشد، ولی بازه ‎$i$‎ با بازه ‎$k$‎ اشتراک نداشته باشد.

می‌دانیم دو بازه با هم اشتراک دارند اگر و فقط اگر در بیش از یک نقطه مشترک باشند.

هپید دلش می‌خواست کمترین مقدار ‎$x$‎ را پیدا کند؛ ولی از آن‌جا که مغزش خیلی خیلی کوچک است، نتوانست این کار را انجام دهد و گریه‌اش گرفت. از آن‌جا که هپید لیاقت این خوش‌حالی را دارد، به او کمک کنید و الگوریتمی چندجمله‌ای ارائه کنید که کمترین مقدار ‎$x$‎ را بیابد و بازه‌ها را با ‎$x$‎ رنگ، رنگ‌آمیزی کند.

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