首页 > 代码库 > 活动安排问题
活动安排问题
题意:
假设现在有N项工作,分别在 Si 时刻开始,在 Ti 时刻结束,对于每项工作可以选择做或者不做,但不可以同时选择时间重叠的工作(即使是开始的瞬间和结束的瞬间重叠也是不允许的)。要求尽可能的多做几件事,那么最多能做几件事呢?
关键在于选择的策略:
优先选择时间最少的?F
优先选择开始最早的?F
优先选择最早结束!!Y
1 #include<iostream> 2 #include<algorithm> 3 using namespace std; 4 struct Act 5 { 6 int start; 7 int end; 8 }; 9 bool compare(Act a,Act b) 10 { 11 return a.end<b.end;//优先选择最早结束的 12 } 13 14 int main() 15 { 16 int n; 17 while(cin>>n) 18 { 19 Act *act=new Act[n+1]; 20 act[0].start=-1; 21 act[0].end=-1; 22 for(int k=1;k<=n;k++) 23 cin>>act[k].start>>act[k].end; 24 sort(act,act+(n+1),compare); 25 int num=0; 26 int i=0; 27 for(int j=1;j<=n;j++) 28 { 29 if(act[j].start>act[i].end) 30 { 31 i=j; 32 num++; 33 } 34 } 35 cout<<num<<"\n"; 36 delete []act; 37 } 38 return 0; 39 }
活动安排问题
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。