点击获取原题链接
活动选择 Time Limit: 1000MS Memory Limit: 65536KB Problem Description 学校的大学生艺术中心周日将面向全校各个学院的学生社团开放，但活动中心同时只能供一个社团活动使用，并且每一个社团活动开始后都不能中断。现在各个社团都提交了他们使用该中心的活动计划（即活动的开始时刻和截止时刻）。请设计一个算法来找到一个最佳的分配序列，以能够在大学生艺术中心安排不冲突的尽可能多的社团活动。 比如有5个活动，开始与截止时刻分别为：  最佳安排序列为：1,4,5。 Input 第一行输入活动数目ｎ（0<ｎ<100）； 以后输入ｎ行，分别输入序号为1到ｎ的活动使用中心的开始时刻ａ与截止时刻ｂ（a,b为整数且0<=a,b<24，a,b输入以空格分隔）。 Output 输出最佳安排序列所包含的各个活动（按照活动被安排的次序，两个活动之间用逗号分隔）。 Example Input 6 8 10 9 16 11 16 14 15 10 14 7 11 Example Output 1,5,4 Hint Author /*****贪心策略：将活动结束时间排序 然后判断下一个活动是否大于等于活动结束而时间****/ #include <bits/stdc++.h> using namespace std; struct node ///结构体存放每一个活动的起止时间 { int a;///开始时间 int b;///结束时间 int c;///活动的进行时间 int id=1;///编号 } a[100+10]; int cmd(node a,node b) { if(a.b != b.b)///结束间不同 结束开始时间 升序 { return a.b < b.b; } else /// 结束时间相同 { return a.c < b.c;/// 活动时间 降序 } } int main() { int n; cin>>n; for(int i=0; i<n; i++) { cin>>a[i].a>>a[i].b; a[i].c=a[i].b-a[i].a;///活动的时间 a[i].id=i+1; } /*****将活动 结束时间排序,如果时间 结束时间相同则按时间大小升序******/ sort(a,a+n,cmd); int time=0;///上一个活动结束时间 int flag=0;///判断 ， for(int i=0; i<n; i++) { if(a[i].a>=time)///上一个活动已结束 { if(flag==0) { flag++; } else cout<<','; cout<<a[i].id; time=a[i].b;///更新数据 } } cout<<endl; return 0; }