#include #include #ifndef EVAL #define STDIO #endif typedef struct { int s, e; } interval; int N; interval *I; int *perm; int *dominatedSet, dominatingNumber; int cmp(const void* a, const void* b); int length(interval i); int overlap(interval A, interval B); int main() { FILE *in, *out; int i, j; #ifdef STDIO in = stdin; out = stdout; #else in = fopen("input.txt", "r"); out = fopen("output.txt", "w"); #endif fscanf(in, " %d", &N); I = (interval*) calloc (N, sizeof(interval)); dominatedSet = (int*) calloc (N, sizeof(int)); perm = (int*) calloc (N, sizeof(int)); for ( i = 0 ; i < N ; i++ ) { fscanf(in, " %d %d", &(I[i].s), &(I[i].e)); dominatedSet[i] = 0; perm[i] = i; } qsort(perm, N, sizeof(int), cmp); dominatingNumber = 0; for ( i = 0 ; i < N ; i++ ) if ( ! dominatedSet[ perm[i] ] ) { dominatedSet[ perm[i] ] = 2; dominatingNumber++; for ( j = 0 ; j < N ; j++ ) if ( ! dominatedSet[ j ] && overlap(I[ perm[i] ], I[ j ]) ) dominatedSet[ j ] = 1; } fprintf(out, "%d\n", dominatingNumber); for ( i = 0 ; i < N ; i++ ) if ( dominatedSet[ perm[i] ] == 2 ) fprintf(stderr, "%d ", perm[i]); return 0; } int overlap(interval A, interval B) { if ( A.e < B.s || B.e < A.s ) return 0; else return 1; } int cmp(const void* a, const void* b) { interval A = I[ * ((int*) a) ]; interval B = I[ * ((int*) b) ]; return length(B) - length(A); } int length(interval i) { return i.e - i.s + 1; }