Fişierul intrare/ieşire:ssecvint.in, ssecvint.outSursăOlimpiada pe scoala clasele a 11-a si a 12-a, 2018
AutorDin FolclorAdăugată devmanzVictor Manz vmanz
Timp execuţie pe test0.2 secLimită de memorie16384 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Ssecvint

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.inssecvint.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici