2151活动选择 简单贪心算法(注释很详细)

注意:根据样例可知,前一个活动的结束时间可以与后一个活动的开始时间重合

//贪心规则:在完成当前的活动后,礼堂选取结束时间早的活动作为下一个活动
//结束时间早,意味着等待时间与活动时间加起来短

#include<bits/stdc++.h>

using namespace std;

pair <int,int> act[1005];

int now;//表示当前时间

int i = 1;

int n;

int cnt;//用于记录开办的活动数

int main()
{
	scanf("%d",&n);
	getchar();
	
	for(i = 1; i <= n; i++)
	{
		scanf("%d %d",&act[i].second,&act[i].first);
		//为了方便下面sort函数的使用,这里的first储存结束时间,secon储存开始时间
	}

	sort(act+1,act+n+1);
	//传入pair的话,默认依据first的大小按升序排序
	//second作为第二判断条件
	
	now = 0;
	//最开始的时间是0
	for(i = 1; i <= n; i++)
	{
		if(act[i].second >= now)
		//如果该活动的开始时间在现在的时间之后
		//由于是排好序的,所以满足这个条件的第一个活动就是结束时间最早的活动
		{
			now = act[i].first;
			cnt++;
		}
	}

	cout << cnt;
	
	return 0;
}