h2(#rays). 'Rays':problema/rays

h2(#rays). 'Rays':problema/rays
 
Pentru fiecare din cele $2$ semiplane determinate de axa Oy rezolvam problema si adunam in final rezultatele. Sa presupunem ca vrem sa aflam numarul minim de raze ce trebuiesc proiectate astfel incat sa distrugem toate segmentele verticale cu {$y > 0$}. Sortam dupa unghi capetele segmentelor verticale date. Astfel, fiecare segment va avea de fapt asociat un interval "de unghiuri". Daca anumite intervale "de unghiuri" se intersecteaza, atunci poate fi dusa o raza care sa elimine toate segmentele aferente acestor intervale.
Problema se reduce la a determina numarul minim de puncte pentru un set de intervale dat astfel incat fiecare interval sa contina cel putin unul din punctele determinate. Aceasta problema se poate rezolva optim in {$O(N log N)$} folosind metoda greedy. Fiecare interval determina doua tipuri de evenimente: "de intrare" (capatul din stanga, mai mic) si "de iesire" (capatul din dreapta, mai mare). Sortam evenimentele pentru toate cele $N$ intervale si realizam o baleiere. In momentul in care ajungem la un punct de intrare, introducem intr-o coada intervalul asociat evenimentului. Atunci cand se intalneste un eveniment de iesire, se aduna $1$ la solutie si se goleste coada, fara a mai considera vreodata evenimentele ce apartin unor intervale deja eliminate.