Palmieri

Problema se rezolvă cu o abordare de tip greedy. Iniţial, ordonăm crescător punctele după abscisă. Primul punct trebuie să fie acoperit de un dreptunghi şi observăm că este inutil să plasăm acest dreptunghi atlfel decât cu latura verticală stângă pe acest punct. Continuăm să parcurgem punctele mai departe şi să le acoperim cu acelaşi dreptunghi până când acesta depăşeşte aria A. În acest moment, putem ignora punctele deja acoperite şi observăm că rămâne de rezolvat aceeaşi problemă pentru un număr strict mai mic de puncte. Pasul pentru determinarea numărului de dreptunghiuri necesare are complexitate O(N), deoarece vom parcurge fiecare punct în parte o singură dată. Complexitatea totală este O(NlogN) din cauza sortării iniţiale.