| Fişierul intrare/ieşire: | ssecvint.in, ssecvint.out | Sursă | Olimpiada pe scoala clasele a 11-a si a 12-a, 2018 |
| Autor | Din Folclor | Adăugată de |  Victor Manz •vmanz |
| Timp execuţie pe test | 0.2 sec | Limită de memorie | 16384 kbytes |
| Scorul tău | N/A | Dificultate |   2/5 |
Poti vedea testele pentru aceasta problema accesand atasamentele.Ssecvint (clasele 11 și 12)
O subsecvenţă a unui şir S = (s1, s2, .., sn) este un subşir format din elemente aflate pe poziţii consecutive în şir: si, si+1, .., si+k-1 unde k este un număr natural (secvenţa poate avea şi lungimea 1).
Fie S un şir de intervale închise de forma [Ai, Bi]. Se cere lungimea maximă pe care o poate avea o subsecvenţă a sa, cu proprietatea că intervalele care fac parte din subsecvenţă au intersecţia nevidă.
Date de intrare
Fişierul de intrare ssecvint.in conţine pe prima linie numărul de intervale N, iar pe următoarele N linii câte două numere întregi Ai şi Bi , separate prin câte un spaţiu. Acestea reprezintă capetele intervalelor date.
Date de ieşire
În fişierul de ieşire ssecvint.out se va scrie un singur număr natural LMAX reprezentând lungimea maximă a unei subsecvenţe de intervale cu intersecţia nevidă.
Restricţii
- 1 ≤ N ≤ 100 000
- -1 000 000 000 ≤ A i ≤ B i ≤ 1 000 000 000
Exemple
| ssecvint.in | ssecvint.out |
|---|---|
| 3 -1 4 2 2 -3 0 | 2 |
| 4 -1 4 2 2 3 6 -3 0 | 2 |
Explicaţie
În ambele exemple subsecvenţa de lungime maximă e formată din primele două intervale.
