2152整数区间 简单贪心算法(注释很详细)

    先说改进版:在第二个for循环做了一点剪枝提升性能

//贪心规则:每次都在最早出现的右端点处取一点加入集合中
/*取点之后向左扫描左端点,扫到的就判断该区间的右端点是否在该点右边
如果在的话就清除该区间防止重复计算*/

#include<bits/stdc++.h>

int n;

std::pair <int,int> s[10005];//区间section

int now;//用于记录当前点

int cnt;//用于计数

int i,j;

int main()
{
	scanf("%d",&n);
	getchar();
	
	for(i = 1; i <=n; i++)
	{
		scanf("%d %d",&s[i].second,&s[i].first);
		//为了方便下面的sort函数,将first表示右端点,second表示左端点
	}
	
	sort(s+1,s+n+1);
	//按右端点排好
	//传入pair的话,默认依据first的大小按升序排序
	//second作为第二判断条件
	
	for(i = 1; i <=n; i++)
	{
		if(s[i].first != -1)
		//如果区间未被消除的话
		{
			now = s[i].first;//在此区间的右端点处打点
			cnt++;//集合点数加一
			
			for(j = i; j <=n; j++)
			//向左扫其他区间的左端点
			//由于在右端点first相同的时候,pair按左端点second升序排列,所以更大的j对应更大的左端点
			{
				
				if(s[j].second > now)
				//如果左端点比打点处都大了,该点就一定不在此区间内了
				//此后的区间也不包括该点
				{
					break;
					//剪枝
				}
				
                if(s[j].first >= now)
                //如果左扫到左端点的区间 的右端点在打的点后面或与其重合,
                {
                	//则可以消除此区间
                	s[j].first = -1;
                	s[j].second = -1;
				}
			}
		}
	}
	
	std::cout << cnt ;
	
	return 0;
}

    如果不想这么麻烦的话,就这个题的数据规模来说,不剪枝也可以通过.如下:

//贪心规则:每次都在最早出现的右端点处取一点加入集合中
/*取点之后扫描所有区间,判断是否包括该点,如果包括话就清除该区间防止重复计算*/

#include<bits/stdc++.h>

int n;

std::pair <int,int> s[10005];//区间section

int now;//用于记录当前点

int cnt;//用于计数

int i,j;

int main()
{
	scanf("%d",&n);
	getchar();

	for(i = 1; i <=n; i++)
	{
		scanf("%d %d",&s[i].second,&s[i].first);
		//为了方便下面的sort函数,将first表示右端点,second表示左端点
	}

	sort(s+1,s+n+1);
	//按右端点排好
	//传入pair的话,默认依据first的大小按升序排序
	//second作为第二判断条件

	for(i = 1; i <=n; i++)
	{
		if(s[i].first != -1)
		//如果区间未被消除的话
		{
			now = s[i].first;//在此区间的右端点处打点
			cnt++;//集合点数加一

			for(j = 1; j <=n; j++)
			{
                if(s[j].second <= now && s[j].first>= now)
				//扫描全部区间,如果左端点在该点以左,右端点在该点以右
                {
                	//则可以消除此区间
                	s[j].first = -1;
                	s[j].second = -1;
				}
			}
		}
	}

	std::cout << cnt ;

	return 0;
}