Timp de executie: $1 secunda/test$
Exemplu:

|_. segment.in |_. segment.out |

|_. segment.in |_. segment.out |_. Figura |

|^. $5$
$2 9 13  9$
$4 6 12  6$
$1 2  6  2$
$5 0  5  8$

$7 5  7 11$  |^. $4$ |

$7 5  7 11$  |^. $4$ |=. !arbori-de-intervale?figure1.jpg! |
 
Folosind cunostinte generale de geometrie analitica se poate obtine un algoritm $O(N^2^)$ dar acesta nu se va incadra in limita de timp.
 
 
h2. Algoritmi de "baleiere" _(line sweeping)_
 
Pentru rezolvarea acestei probleme vom folosi o tehnica cunoscuta sub numele de "baleiere" _(sweeping)_ care este comuna multor algoritmi de geometrie computationala. In baleiere, o dreapta de baleiere verticala, imaginara, traverseaza multimea obiectelor geometrice, de obicei de la stanga la dreapta.  Baleierea ofera o metoda pentru ordonarea obiectelor geometrice, plasandu-le intr-o structura de date, pentru obtinerea relatiilor dintre ele.
 
Algoritmii de baleiere gestioneaza doua multimi de date:
 
# +Starea liniei+ de baleiere da relatia dintre obiectele intersectate de linia de baleiere
# +Lista punct-eveniment+ este o secventa de coordonate $x$, ordonate de la stanga la dreapta de obicei, care definesc pozitiile de oprire ale dreptei de baleiere; fiecare astfel de pozitie de oprire se numeste _punct eveniment_; numai in punctele eveniment se intalnesc modificari ale starii liniei de baleiere; pentru unii algoritmi, lista punct-eveniment este determinata dinamic in timpul executiei algoritmului.
 
Pentru a rezolva problema, vom deplasa o dreapta de baleiere verticala, imaginara de la stanga la dreapta. Lista punct-eveniment va contine capetele segmentelor orizontale, ce fel de tip sunt (cap stanga sau cap dreapta) si segmentele verticale. Pe masura ce ne deplasam de la stanga la dreapta vom efectua urmatoarele operatii:
 
* cand intalnim un capat stang, inseram capatul in starile dreptei de baleiere;
* cand intalnim un capat drept, stergem capatul din starile dreptei de baleiere;
* cand intalnim un segment vertical, numarul de intersectii ale acestui segment cu alte segmente orizontale va fi dat de numarul capetelor de intervale care se afla in starile dreptei de baleiere cuprinse intre coordonatele $y$ ale segmentului vertical.