#include #include int N; int intervals[150000][2]; int covers[150000]; //ci salverò il numero di intervalli che ogni intervallo copre int max = 0, index = 0; int preso[150000]; int total = 0; int continua = 1; int size[150000]; int min, indexMin; int main (){ FILE *in, *out; int i, j; in = fopen("input.txt", "r"); if (in == NULL){ printf("Errore nella lettura del file\n"); return -1; } fscanf(in, "%d", &N); for(i = 0; i < N; i++){ fscanf(in, "%d %d", &intervals[i][0], &intervals[i][1]); size[i] = intervals[i][1] - intervals[i][0]; } for(i = 0; i < N; i++){ covers[i] = 0; preso[i] = 0; } //cerco, per ogni itervallo, quanti intervalli copre for(i = 0; i < N-1; i++){ //guardo gli intervalli dopo for(j = i+1; j < N; j++){ if(intervals[i][1] > intervals[j][0]) covers[i]++; else break; } } for(i = 1; i < N; i++){ //guardo gli intervalli prima for(j = i-1; j >= 0; j--){ if(intervals[i][0] < intervals[j][1]) covers[i]++; else break; } } while(continua){ //cerco l'intervallo con dimensioni più piccole che non è ancora stato preso min = 150000; //controlla, ma è per dire tanto! indexMin =-1; for(i = 0; i < N; i++){ if(size[i] < min && preso[i] == 0){ min = size[i]; indexMin = i; } } //tra tutti gli interalli che intersecano quello appena trovato, prendo quello che ha maggiori intersezioni max = 0; index = indexMin; for(i = indexMin+1; i < N; i++){ //cerco l'intervallo che interseca questo e che interseca il maggior numero di intervalli if(intervals[indexMin][1] > intervals[i][0] && covers[i] > max){ index = i; max = covers[i]; } } for(i = indexMin-1; i >= 0; i--){ //cerco l'intervallo che interseca questo e che interseca il maggior numero di intervalli //printf("covers[%d] = %d > max: %d\n", i, covers[i], max); if(intervals[indexMin][0] < intervals[i][1] && covers[i] > max){ index = i; max = covers[i]; } } total++; preso[index] = 1; for(i = index+1; i < N; i++){ //controllo quelli dopo if(intervals[index][1] > intervals[i][0]) preso[i] = 1; else break; } for(i = index-1; i >= 0; i--){ //controllo quelli prima if(intervals[index][0] < intervals[i][1]) preso[i] = 1; else break; } continua = 0; for(i = 0; i < N; i++){ if(preso[i] == 0){ continua = 1; break; } } } out = fopen("output.txt", "w"); fprintf(out, "%d", total); return 0; }