TZOJ:区间问题
时间:2022-05-07 16:27
描述
有n项工作,每项工作分别在 si时间开始,ti时间结束。对于每项工作你选择参与与否,如果选择 了参与,那么自始至终就必须全程参与。参与工作的时间段不可以重叠(即使是开始的瞬间和结束的瞬间重叠也是不允许的) 。
你的目标是参与尽可能多的参与工作,那么最多能参与多少项工作呢?
输入
输入数据有多组,每组数据:
第一行为正整数n(1<=n<=10^5),表示工作的数目;
第二行有n个整数,表示每项工作的起始时间si;
第三行有n个整数,表示每项工作的结束时间ti。
1<=si<=ti<=10^9
输入以EOF结束。
输出
每组输出一个整数,表示最多能参与的工作数目。
样例输入
样例输出
解题思路:按照结束时间快排一下,自己想一下就清楚了。
菜鸡的成长史 ^-^
1 #include2 using namespace std; 3 struct node 4 { 5 int x,y; 6 }A[100006]; 7 bool cmp(node a,node b) 8 { 9 if(a.y!=b.y) //按照结束时间进行排序 10 return a.y >n) 18 { 19 for(int i=1;i<=n;i++) 20 cin>>A[i].x; 21 for(int i=1;i<=n;i++) 22 cin>>A[i].y; 23 sort(A+1,A+1+n,cmp); 24 int sum=1; 25 for(int i=1,j=i+1;i<=n-1,j<=n;j++) 26 { 27 if(A[i].y View Code