سوال ۷
«هپید» در جشن تولد خود $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$ رنگ، رنگ‌آمیزی کند.
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
