2213005_ac_403ms_132k.cpp

来自「北大大牛代码 1240道题的原代码 超级权威」· C++ 代码 · 共 82 行

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

using namespace std;

struct node
{
	int a;
	int b;
	int e;
}inter[10001];

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

void input()
{
	int n, i, j;
	int ans;

	scanf("%d",&n);
	for(i = 0; i < n; i++)
	{
		inter[i].e = 2;
		scanf("%d%d",&inter[i].a,&inter[i].b);
	}
	sort(inter,inter+n,cmp);
	for(i = 0; i < n; i++)
		for(j = i+1; j < n; j++)
		{
			if(inter[j].a<=inter[i].b)
                               {if(inter[j].b<=inter[i].b)
				inter[i].e = 0;}
			else
				break;
		}
	ans = 0;
	for(i = 0; i < n; i++)
	{
		if(inter[i].e==2)
		{
			for(j = i+1; j < n; j++)
			{
				if(inter[j].a>inter[i].b)
					break;
				if(inter[j].e)
				{
					if(inter[j].a<inter[i].b)
						inter[j].e = 0;
					else
						inter[j].e--;
				}
			}
			ans += 2;
		}
		else
			if(inter[i].e==1)
			{
				for(j = i+1; j < n; j++)
				{
					if(inter[j].a>inter[i].b)
						break;
					if(inter[j].e)
							inter[j].e--;
				}
				ans++;
			}
	}
	printf("%d\n",ans);
}

int main()
{
	input();
	return 1;
}