int

Int

== include(page="template/taskheader" task_id="int") ==
 
Poveste ...
 
h2. Cerinta
 
...
 
h2. Restrictii
 
...
 
h2. Date de intrare
 
...
 
h2. Date de iesire
 
...
 
h2. Exemplu
 
| int.in | int.out |
| linia1
linia2
linia3
| linia1
linia2
|
 
== include(page="template/taskfooter" task_id="int") ==

==Include(page="template/taskheader" task_id="int")==
==Include(page="template/raw")==
 
Int
 
 
 
Se dau N intervale deschise (capetele nu fac parte din interval), situate pe axa OX. Determinati o submultime de intervale cu numar maxim de elemente, cu proprietatea ca intersectia oricaror 2 intervale din submultime este vida.
 
h2. Date de Intrare
 
Prima linie a fisierului de intrare int.in contine numarul N de intervale. Urmatoarele N linii contin cate doua numere intregi, A si B, reprezentand capatul stanga, respectiv capatul dreapta al cate unui interval.
 
h2. Date de Iesire
 
In fisierul de iesire int.out veti afisa numarul de elemente al submultimii determinate.
 
h2. Restrictii si precizari
 
o 1 <= N <= 50.000
o Pentru fiecare interval avem -2.000.000.000 <= A < B <= 2.000.000.000
o 40% din fisierele de test vor avea N <= 2000
 
h2. Exemplu
 
 
 
 
|int.in|int.out|Explicatii |
 
|5 |3 |Submultimea ar putea contine intervalele (-11,-7) , (0,1) si|
| | |(1,6). |
|-3 10 | | |
| | | |
|-11 -7| | |
| | | |
|1 6 | | |
| | | |
|0 1 | | |
| | | |
|0 30 | | |
 
 
 
==Include(page="template/taskfooter" task_id="int")==