pku1716.cpp

来自「这是ACM 方面的资料 是PKU的 北京大学的出来的」· C++ 代码 · 共 59 行

#include <stdio.h>
#include <algorithm>
using namespace std;
typedef struct Node
{
	int s, e;
}Node;

const int size = 10002;
Node nd[size];
int N;

bool cp(Node a, Node b)
{
	return a.e < b.e;
}

bool In(int a, int b, int c)
{
	return a <= b && b <= c;
}

int main()
{
	int i, p, q, ans;
	scanf("%d", &N);

	for (i = 0; i < N; i++)
	{
		scanf("%d %d", &nd[i].s, &nd[i].e);
	}

	sort(nd, nd + N, cp);
	
	ans = 2;
	p = nd[0].e - 1;
	q = p + 1;
	for (i = 1; i < N; i++)
	{
		if (In(nd[i].s, p, nd[i].e))
		{
			continue;
		}
		else if (In(nd[i].s, q, nd[i].e))
		{
			ans += 1;
			p = q;
			q = nd[i].e;
		}
		else
		{
			ans += 2;
			p = nd[i].e - 1;
			q = nd[i].e;
		}
	}
	printf("%d\n", ans);
	return 0;
}