1400.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1400 on 2005-12-19 at 19:45:26 */ 
#include <cstdio>
#include <cstring>

const int MAX = 512000;

int next[MAX];

int main()
{
	int n, m, i;
	int t, T;

	scanf("%d", &T);
	for(t = 0; t < T; t++) {
		memset(next, 0, sizeof(next));
		scanf("%d %d", &n, &m);
		for(i = 0; i < m; i++) {
			int b, e;
			scanf("%d %d", &b, &e);
			if(next[b] < e) next[b] = e;
		}
		int cur = 1, used = 0, prev = 1;
		while(cur < n) {
			int max = 0;
			for(i = prev; i <= cur; i++) {
				if(next[i] > max) max = next[i];
			}
			prev = cur;
			cur = max;
			used++;
		}
		printf("%d\n", used);
	}

	return 0;
}