博客

题目：

设有n个任务，其中每个任务有一个起始时间si和一个结束时间ei，且si<ei，同一时间只能完成一个任务。如果选择了任务i ，则它在时间区间 [si ,ei) 内占用资源。若区间 [si ,ei) 与区间 [sj, ej)不相交，则称任务 i 与任务 j 是相容的。那么，对于给定的任务时间区间，能互相兼容的最大任务个数是多少呢？

输入格式:


第一行一个整数n （1<=n<=1000） ；

接下来n行，每行两个整数si 和 ei。

输出格式:


互相兼容的最大任务个数。

输入样例:


4

1 3

4 6

2 5

1 7

输出样例:


2

一个任务有开始时间、任务时长和结束时间。将问题

简化

，只根据任务结束时间，从早到晚进行排序。越早结束的任务，就有越多的时间来完成剩下的任务，之后比较前一个任务的结束时间和后一个任务的开始时间，就可以确定任务是否可兼容。

#include<iostream>
#include<algorithm>
using namespace std;
struct task{
	int s;//开始时间 
	int e;//结束时间 
};
bool cmp(struct task a,struct task b)
{
	return a.e<b.e;//根据任务结束时间，从早到晚排序 
}
int main()
{
	int i,n,sum=1;//不管怎样，最少都可以完成一个任务 
	struct task t[1020];
	cin>>n;
	for(i=0;i<n;i++)
		cin>>t[i].s>>t[i].e;
	sort(t,t+n,cmp);
	int last=t[0].e; 
	for(i=1;i<n;i++)
	{
		if(t[i].s>=last)
		{
			last=t[i].e;//更新
			sum++;
		}
	}
	cout<<sum;
	return 0;
}