یک قاب عکس به عرض $W$ و ارتفاع $H$ داریم. تعدادی عکس داریم که عرض و ارتفاع هر‌یک از آن‌ها مشخص شده‌است و هر یک به تنهایی در قاب عکس جا می‌شود. واضح است که نمی‌توان عکس‌ها را دوران داد. می‌خواهیم تا جای ممکن این عکس‌ها را در قاب عکس قرار دهیم به طوری که عکس‌ها هم‌پوشانی نداشته باشند.
الگوریتم زیر را در نظر بگیرید:

1. عکس‌ها را بر اساس ارتفاع به صورت نزولی مرتب کنید.
2. اولین عکس باقی‌مانده را در پایین‌ترین نقطه از ضلع سمت چپ که هیچ عکسی در آن نیست قرار دهید، اگر نمی‌توانید این عکس را قرار دهید به الگوریتم پایان دهید.
3. سپس عکس‌ها را یکی پس از دیگری در سمت راست آخرین عکس̥ گذاشته شده قرار دهید به طوری که نقطه پایین راست عکس قبلی و نقطه پایین چپ عکس کنونی منطبق شوند. این کار را تا زمانی که عکسی باقی‌مانده است و عکسی از سمت راست قاب عکس خارج نشده است انجام دهید.
4. اگر عکسی باقی‌مانده است به ۲ بروید.

نشان دهید اگر $w$ و $h$ به ترتیب بیشینه‌ی عرض و ارتفاع عکس‌ها باشند؛ پس از پایان الگوریتم یا همه‌ی عکس‌ها درون قاب عکس قرار می‌گیرند یا حداقل $(W - w) \times (H - h)$ از مساحت قاب عکس را پوشیده می‌شود.

با توجه به الگوریتم، عکس‌هایی که در شکل بالا وجود دارند مطابق تصویر در قاب عکس قرار می‌گیرند. در مثال بالا دو قطعه عکس در قاب جای نمی‌گیرد.

• سوال بعد