Fişierul intrare/ieşire:planificare.in, planificare.outSursăAlgoritmiada 2012, Runda 2
AutorCosmin GheorgheAdăugată deCezarMocanCezar Mocan •CezarMocan
Timp execuţie pe test0.1 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Planificare

Talent Day se apropie la trustul TV Blomkvist, iar presedintele Mike are nevoie de voi pentru a realiza grila de programe. N participanti s-au inscris pentru a isi expune talentele, fiecare comunicand intervalul de timp de care are nevoie. Lantul TV al lui Mike este format din K posturi, (Blomkvist 1, Blomkvist 2, ... Blomkvist K) care transmit independent unul de altul. Din cauza ca toate cele K posturi sunt la fel de populare, participantilor le este indiferent la care vor aparea. Stiind ca la orice moment orice post va transmite un singur show, determinati care este numarul maxim de show-uri care pot fi televizate.

Date de intrare

Fişierul de intrare planificare.in va contine pe prima linie 2 numere naturale, N si K. Pe fiecare din urmatoarele N linii se vor afla cate 2 valori, starti si stopi, reprezentand intervalul de timp in care participantul i isi poate desfasura activitatea.

Date de ieşire

Fişierul de ieşire planificare.out va contine pe prima linie numarul cerut de Mike.

Restricţii si precizari

  • 1 ≤ N ≤ 100.000
  • 1 ≤ K ≤ 100.000
  • 1 ≤ starti ≤ stopi ≤ 1.000.000.000
  • Pentru 30% din teste, N ≤ 2000, iar pentru alte 10% din teste, K = 1
  • La fiecare televiziune un show poate sa inceapa chiar in acelasi moment in care s-a terminat precedentul.

Exemplu

planificare.inplanificare.out
2 1
1 4
4 8
2
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content