简单贪心 区间调度问题

简单贪心 区间调度问题

有n项工作，每项工作分别在si时间开始，在ti时间结束。对于每项工作
，你都可以选择 参与与否 ，如果选择了参与，那么自始至终都必须全程参加
。此外，参与工作的时间段 不能重叠（即使是开始的瞬间和结束的瞬间的重叠也是
不允许的） 。 


限制 
0<=c1,c5,c10,c50,c100,c500<=10^9
0<=A<=10^9

输入
5 1 2 4 6 8 3 5 7 9 10
输出 

3

按照结束时间排序即可

#include<iostream>
#include<algorithm>
using namespace std;#define MAX_N 100000
int n;pair<int,int> p[MAX_N];bool cmp(pair<int,int> a,pair<int,int> b)
{return a.second<b.second; 
} int solve()
{int t=0,count=0;for(int i=0;i<n;i++){if(t<p[i].first){count++;t=p[i].second;}}return count;
}int main()
{cin>>n;for(int i=0;i<n;i++){cin>>p[i].first;}for(int i=0;i<n;i++){cin>>p[i].second;}sort(p,p+n,cmp);
//	 for(int i=0;i<n;i++)
//	 {
//	 	cout<<p[i].first<<endl;
//	 	cout<<p[i].second<<endl;
//	 }cout<<solve()<<endl;
}