#include #include #define MAXN 10000 #define DEBUG 1 int r[ MAXN ], l[ MAXN ], n, selected; void read_input() { int i; scanf( "%d", &n ); for ( i = 0; i < n; i++ ) scanf( "%d %d", &l[ i ], &r[ i ] ); } void search() { int x, i, ci, vi, j, cj, vj; x = 0; for (;;) { i = -1; vi = INT_MAX; for ( ci = 0; ci < n; ci++ ) { if ( x <= l[ ci ] ) if ( r[ ci ] < vi ) { i = ci; vi = r[ ci ]; } } if ( i < 0 ) break; j = -1; vj = -1; for ( cj = 0; cj < n; cj++ ) { if ( x <= l[ cj ] && l[ cj ] <= r[ i ] ) if ( r[ cj ] > vj ) { j = cj; vj = r[ cj ]; } } if ( DEBUG ) fprintf( stderr, "%d %d\n", l[ j ], r[ j ] ); selected++; x = r[ j ] + 1; } } int main() { #ifdef EVAL freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif read_input(); search(); printf( "%d\n", selected ); return 0; }