تعدادی مستطیل با ارتفاع (اندزه‌ی ضلع عمودی) یکسان در صفحه داده شده‌اند؛ اضلاع مستطیل‌ها به موزات محور‌های مختصات می‌باشند. غایت آن است که برخی از مستطیل‌ها را رنگ کنیم، به‌طوری که اشتراک هیچ دو مستطیل رنگ شده‌ای مساحت مثبت نداشته باشد.

فرض کنید که با شرط فوق بیش‌ترین مساحتی را که می‌توان رنگ‌ کرد $\gamma$ باشد. این بار نیز الگوریتمی چند جمله‌ای ابداع کنید که با در نظر گرفتن شرایط فوق، دست کم مساحتی را به اندازه‌ی $\frac{\gamma}{2}$ رنگ نمایید.

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