Studenti

Fie Gmax si Hmax greutatea maxima a unui student, respectiv inaltimea maxima a unui student. Distingem doua cazuri elementare de a repartiza studentii in sali. Primul caz este sa plasam atat studentul cu cea mai mare inaltime cat si studentul cu cea mai mare greutate in aceiasi sala, sa spunem ca ii plasam in sala S1. Atunci este clar ca in celelalte doua sali se va afla cate un singur student, deoarece orice student poate intra in sala S1 fara sa modifice greutatea sau intaltimea maxima din sala. Astfel complexitatea pentru acest caz este O(N²). Al doilea caz elementar este cand Gmax si Hmax se afla in sali diferite. Sa spunem ca studentul cu greutatea Gmax il vom repartiza in sala S1 iar cel cu intaltimea Hmax in sala S2. Vom lua fiecare posibilitate de a fixa inaltimea maxima din sala S1 si greutatea maxima din sala S2. Apoi iteram prin fiecare student in parte si vedem daca el poate fi repartizat in S1 sau S2 fara sa modifice greutatea maxima sau inaltimea maxima din sala respectiva. Daca nu poate fi repartizat in S1 sau S2 il repartizam in S3. Complexitatea acestui caz este O(N³).