Fişierul intrare/ieşire: | int.in, int.out | Sursă | Happy Coding 2006 |
Autor | Mugurel Ionut Andreica | Adăugată de | |
Timp execuţie pe test | 0.275 sec | Limită de memorie | 65536 kbytes |
Scorul tău | N/A | Dificultate |
Vezi solutiile trimise | Statistici
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.
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.
Date de iesire
In fisierul de iesire int.out veti afisa numarul de elemente al submultimii determinate.
Restrictii si precizari
- 1 ≤ N ≤ 50.000
- Pentru fiecare interval avem -2.000.000.000 ≤ A < B ≤ 2.000.000.000
- 40% din fisierele de test vor avea N ≤ 2000
Exemplu
int.in | int.out |
---|---|
5 -3 10 -11 -7 1 6 0 1 0 30 | 3 |
Explicatii
Submultimea ar putea contine intervalele (-11,-7), (0,1) si (1,6)