Fixezi x1, x2 proiectiile pe axa OX ale laturilor paralele cu OY ale dreptunghiului. Pentru ele tii sortate valorile coordonatelor y ale punctelor cu x intre x1 si x2. Dreptunghiurile cu k puncte se pot determina printr-o simpla iteratie.
Asta fac si eu, dar pentru fiecare pereche x
1 si x
2 trebuie facuta acea sortare daca am inteles bine. Dar, de aici rezulta o complexitate de O(N^2 (pt ca iau fiecare pereche) * NlogN(din sortare)) = O(N^3logN)
Ideea e sa o rezolvi fara sa sortezi in O(NlogN). Cand treci de la (x
i, x
j) la (x
i, x
j+1) trebuie sa inserezi intr-un sir sortat valorile coordonatelor y pentru care x=x
j+1. Daca ai si aceste ultime valori sortate, atunci interclasarea lor se face in O(N).