Fişierul intrare/ieşire:int.in, int.outSursăHappy Coding 2006
AutorMugurel Ionut AndreicaAdăugată de
Timp execuţie pe test0.55 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

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.inint.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)

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content