点击获取原题链接
活动选择问题 Time Limit: 1000MS Memory Limit: 65536KB Problem Description sdut 大学生艺术中心每天都有n个活动申请举办，但是为了举办更多的活动，必须要放弃一些活动，求出每天最多能举办多少活动。 Input 输入包括多组输入，每组输入第一行为申请的活动数n(n<100)，从第2行到n+1行，每行两个数，是每个活动的开始时间b，结束时间e； Output 输出每天最多能举办的活动数。 Example Input 12 15 20 15 19 8 18 10 15 4 14 6 12 5 10 2 9 3 8 0 7 3 4 1 3 Example Output 5 Hint Author /**********贪心策略：将活动结束时间升序 如果两个结束时间相同则 按活动持续时间升序 最后在选择活动*******************************/ #include <bits/stdc++.h> using namespace std; struct node { int a;///开始时间 int b;///结束时间 int c;///活动时间 }a[100+100]; 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; while(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;///活动的时间 } sort(a,a+n,cmd); int count=0;///活动的时间 int time =0;///上一个活动结束时间 for(int i=0;i<n;i++) { if(a[i].a >= time )///活动开始 大于 上一个结束时间 { count++; time =a[i].b;///跟新时间 } } cout<<count<<endl; } }