Giri sulla scopa Nimbus3000

Al celebre maghetto Harry Potter è stata regalata una scopa volante modello Nimbus3000 e tutti i suoi compagni del Grifondoro gli chiedono di poterla provare.
Il buon Harry ha promesso che nei giorni a venire soddisferà le richieste di tutti, ma ogni ragazzo è impaziente e vuole provare la scopa il giorno stesso.
Ognuno propone ad Harry un intervallo di tempo della giornata durante il quale, essendo libero da lezioni di magia, può fare un giro sulla scopa, e per convincerlo gli offre una fantastica caramella Tuttigusti+1.
Tenendo presente che una sola persona alla volta può salire sulla Nimbus3000 in ogni istante di tempo, Harry decide di soddisfare, tra tutte le richieste dei ragazzi, quelle che gli procureranno la massima quantità di caramelle (che poi spartirà coi suoi amici Ron e Hermione).

Aiutalo a trovare la migliore soluzione possibile.

Dati di input

Il file input.txt contiene nella prima riga un intero positivo N, che indica il numero di richieste, che sono numerate da 1 a N.
Ognuna delle successive N righe contiene una coppia di interi.
Ciascuna di tali righe contiene una coppia di interi positivi A e B, separati da uno spazio, a rappresentare la richiesta di poter utilizzare la scopa dall’istante inizialeA fino all’istante finale B, in cambio di una caramella (dove A < B).
A tal fine, il tempo è diviso in istanti discreti numerati a partire da 1 in poi.

Dati di output

Il file output.txt è composto da una riga contenente un solo intero, che rappresenta il massimo numero di caramelle che Harry può ottenere.

Assunzioni

• 1 < N < 1000
• Gli interi nelle N coppie sono distinti l’uno dall’altro (non esistono due interi uguali, anche in coppie diverse.

Esempi di input(output

/*
    www.valcon.it
    OII - Fase territoriale - Giri sulla Scopa Nimbus3000
*/

#include
#include  // qsort()

struct richiesta{ int A, B; };

int cmp(const void *a, const void *b)
{
    richiesta r1 = *((const richiesta*)a);
    richiesta r2 = *((const richiesta*)b);

         if(r1.B <  r2.B) return -1;
    else if(r1.B == r2.B) return  0;
    else                  return +1;
}

richiesta richieste[1000];

int main()
{
    int N;
 
    FILE* fin =fopen( "input.txt","r");
    FILE* fout=fopen("output.txt","w");

    fscanf(fin, "%d", &N); 
    for(int i=0; i <  N; i++)
        fscanf(fin, "%d %d", &(richieste[i].A), &(richieste[i].B)); 
    qsort(richieste,N,sizeof(richiesta),cmp); 
 
    int caramelle=1;
    int ultimo=richieste[0].B; 
    for(int r=1; r < N; r++)
    {
        if(richieste[r].A >= ultimo)
        {
            caramelle++;
            ultimo=richieste[r].B;
        }
    }
    fprintf(fout, "%d\n", caramelle);
    return 0;
}