Sa vedem acum analiza complexitatii. Avem nevoie de un timp $O(N * log N)$ pentru sortarea listei de evenimente dupa abscisa, $O(log N)$ (sau chiar $O(1)$ la heap-uri si la $set$-urile din STL) pentru alegerea obiectului cu ordonata maxima, $O(log N)$ pentru inserare si stergere in structura de date aleasa. Intrucat sunt $2 * N$ evenimente (cate 2 capete pentru fiecare segment), iar pentru fiecare efectuam o interogare si o adaugare / stergere, complexitatea finala va fi $O(N * log N) + O(N) * (O(log N) + O(log N)) = O(N * log N)$.

Problema de fata poate fi generalizata pentru cazul in care dreptunghiurile nu au o latura fixata, ci sunt oarecare in plan. Pentru acest lucru, la fiecare eveniment va fi necesara o parcurgere integrala a multimii de obiecte intersectate de linia de baleiere, ceea ce conduce la un timp de executie patratic $O(N^2^)$. Lasam aceasta aplicatie ca un exercitiu pentru cititor.

Situatia se poate complica daca dreptunghiurile nu au o latura fixata pe axa $OX$. Nu mai este suficienta o simpla extragere a elementului maxim din structura de date, ci trebuie sa retinem mult mai multe informatii pentru a pastra complexitatea $O(N * log N)$. Aceasta generalizare a fost data la Olimpiada Baltica de Informatica din 2001 (problema Mars Maps).

h2(#baleiere_rotationala). Baleiere rotationala

h2(#aplicatii). Aplicatii

Iata si o scurta lista de probleme care merita implementate:
 
* BOI 2001: 'Mars Maps':http://www.ii.uni.wroc.pl/boi/index.phtml?id=11
 

h2(#bibliografie). Bibliografie