Numărul maxim de intervale disjuncte

Când două intervale deschise au intersecția vidă

Intervalul deschis (a, b) conține numerele strict mai mari decât a și strict mai mici decât b. Extremitățile nu aparțin intervalului. Două intervale (a₁, b₁) și (a₂, b₂), cu b₁ ≤ b₂, au intersecția vidă dacă și numai dacă a₂ ≥ b₁, adică al doilea începe cel mai devreme în punctul în care se termină primul.

În exemplul din enunț, intervalele (10, 150) și (150, 200) au intersecția vidă: numărul 150 nu aparține niciunuia dintre ele.

Explicarea metodei de rezolvare

Problema se rezolvă prin metoda greedy. Intervalele se ordonează crescător după extremitatea dreaptă, apoi se parcurg în această ordine:

1. Se alege primul interval, cel care se termină cel mai devreme.
2. Se reține extremitatea dreaptă a ultimului interval ales.
3. Fiecare interval următor se alege dacă extremitatea lui stângă este mai mare sau egală cu extremitatea dreaptă reținută. Atunci el nu se intersectează cu niciunul dintre intervalele alese, iar extremitatea reținută devine extremitatea lui dreaptă.
4. Intervalul care începe înainte de extremitatea reținută se intersectează cu ultimul interval ales și nu se alege.

Numărul intervalelor alese este rezultatul cerut.

Corectitudinea criteriului de alegere. Fie G intervalul care se termină cel mai devreme și o selecție oarecare de intervale disjuncte, cu număr maxim de elemente. Dacă primul interval al acestei selecții, în ordinea extremităților drepte, nu este G, el poate fi înlocuit cu G. G se termină cel târziu când se termină intervalul înlocuit, deci toate celelalte intervale ale selecției încep cel mai devreme în punctul în care se termină G și rămân disjuncte de el. Selecția obținută are același număr de intervale, deci există o soluție optimă care conține alegerea greedy. Același raționament se aplică apoi intervalelor a căror extremitate stângă este mai mare sau egală cu extremitatea dreaptă a lui G.

Justificarea eficienței

Timpul de executare al algoritmului se compune din:

• ordonarea celor n intervale, făcută cu funcția sort din biblioteca algorithm, în timp de ordinul O(n log n);
• parcurgerea intervalelor ordonate, o singură dată, cu o comparație pentru fiecare interval, în timp O(n).

Timpul de executare este deci O(n log n), dat de ordonare. Pentru n = 10⁴, algoritmul face un număr de operații de ordinul 10⁵.

Verificarea tuturor submulțimilor de intervale ar da tot rezultatul corect, dar ar cere examinarea a 2ⁿ submulțimi, un număr care pentru n = 10⁴ depășește cu mult ce se poate calcula în timp util.

Memoria folosită este de ordinul O(n), pentru vectorul de intervale. Ordonarea cere ca toate intervalele să fie citite înainte de prelucrare.