Non riesco a risolvere questo problema nonostante credo che la tecnica risolutiva sia giusta.
Gli intervallo sono già ordinati per inizio, il mio algoritmo è questo:
- Prendo il primo intervallo non ancora coperto:
-
- Per tutti gli intervalli che si intersecano con questo
-
-
- Se questo intervallo ha fine maggiore, salva la fine
-
-
- Assegna come nuova copertura la fine maggiore trovata
-
- Aggiungi uno agli intervalli scelti
Non riesco a creare esempi che non funzionino, ho provato input_bonus.txt ed invece di 59 mi ritorna 62, ma non riesco a capire quale non andrebbe preso, sono 5000 intervalli e non riesco a controllarli a mano 
Questo è il codice:
#include <algorithm>
#include <cstdio>
#define MAXN 150010
using namespace std;
struct intervallo_t {
int a, b;
} V[MAXN];
int N;
int main() {
freopen("input_bonus.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
scanf("%d", &N);
for(int i = 0; i < N; i++) {
scanf("%d %d", &V[i].a, &V[i].b);
}
int risultato = 0;
int last_covered = -1;
for (int i = 0; i < N; i++) {
if (V[i].a < last_covered) continue;
printf("Intervallo %d,%d\n", V[i].a, V[i].b);
int j = i+1;
int far = V[i].b;
int took_a = V[i].a;
int took_b = V[i].b;
while (V[j].a < V[i].b && j < N) {
printf("\tControllo anche %d,%d\n", V[j].a, V[j].b);
if (V[j].b > far) {
took_a = V[j].a;
took_b = V[j].b;
far = V[j].b;
}
j++;
}
i = j-1;
printf("Far = %d\n", far);
last_covered = far;
risultato++;
}
printf("%d\n", risultato);
return 0;
}
Grazie