2980224_ac_1402ms_4084k.cc

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <algorithm>

using namespace std;

int n, m;
struct node
{
	int l, r;
}e[500001];

bool cmp(node a,node b)
{
	if(a.l==b.l)
		return a.r < b.r;
	else
		return a.l < b.l;
}

int main()
{
	int i, j, a, b, r;

	scanf("%d%d",&n,&m);
	for(i = 0; i < m; i++)
	{
		scanf("%d%d",&a,&b);
		if(a > b)
		{
			a += b;
			b = a - b;
			a = a - b;
		}
		e[i].l = a;
		e[i].r = b;
	}
	sort(e,e+m,cmp);
	int ans = 0;
	i = 0;
	while(e[i].l==1)
		i++;
	i--;
	r = e[i].r;
	ans++;
	j = i+1;
	while(r < n)
	{
		while(j < m && e[j].l <= r)
			j++;
		ans++;
		r = e[j-1].r;
	}
	printf("%d\n",ans);
	return 0;
}