Programant el vídeo P40128


Statement
 

pdf   zip

thehtml

El professor Oak és un gran seguidor de Humor Amarillo. Tant, que s’ha comprat una antena de satèl·lit per veure el programa a diverses cadenes europees. El professor Oak té una guia de tots els canals d’Europa, i vol programar el seu vídeo per gravar cada dia tants episodis com sigui possible. Però no és fàcil: El vídeo només pot gravar un canal a la vegada. A més, els capítols poden tenir durades diferents (per com estan editats, la publicitat, etcètera).

Podeu ajudar el professor Oak? Feu un programa que, donats els instants d’inici i de final d’emissió de tots els episodis de Humor Amarillo en tots els canals europeus durant diversos dies, calculi el nombre màxim d’episodis que es poden gravar cada dia.

Entrada

L’entrada consisteix en diversos casos. Cada cas té un natural 1 ≤ n ≤ 105 seguit de n parells (i1, f1), …, (in, fn) de naturals que indiquen l’instant d’inici i de final, ambdós inclosos, de cada capítol d’un dia. Per a tot j entre 1 i n, es compleix 0 ≤ ij ≤ fj ≤ 109.

Sortida

Per a cada cas de l’entrada, cal escriure una línia amb el nombre màxim de capítols que el professor Oak podrà gravar sencers aquell dia.

Public test cases

  • Input

    3   100 200  500 780  1000 1040

7   400 1100  500 600  900 1400
200 300  1200 1300  100 700  800 1000

3   0 100  100 1439  0 1439

2   1234 1234  1234 1234

    Output

    3
4
1
1
    • Information
    Author
    Ricardo Martín
    Language
    Catalan
    Other languages
    English
    Official solutions
    C++ Python Python
    User solutions
    C++ Python