题目描述
Problem Description
学校的大学生艺术中心周日将面向全校各个学院的学生社团开放，但活动中心同时只能供一个社团活动使用，并且每一个社团活动开始后都不能中断。现在各个社团都提交了他们使用该中心的活动计划（即活动的开始时刻和截止时刻）。请设计一个算法来找到一个最佳的分配序列，以能够在大学生艺术中心安排不冲突的尽可能多的社团活动。
比如有5个活动，开始与截止时刻分别为：
最佳安排序列为：1,4,5。
Input
第一行输入活动数目ｎ（0<ｎ<100）；
以后输入ｎ行，分别输入序号为1到ｎ的活动使用中心的开始时刻ａ与截止时刻ｂ（a,b为整数且0<=a,b<24，a,b输入以空格分隔）。
Output
输出最佳安排序列所包含的各个活动（按照活动被安排的次序，两个活动之间用逗号分隔）。
Sample Input
6
8 10
9 16
11 16
14 15
10 14
7 11
Sample Output
1,5,4
题目思路
刚看到这道题，还是有点懵逼的。
总结一下题目的大致意思：给你N个活动，每个活动有对应的开始和结束以及编号，让你找一个最合适的方法，来使进行的活动最多。
直接开一个结构体，里面包含每个活动的开始、结束、编号、时间区间，这里的时间区间主要是为了后面排序使用，对于结构体进行排序，依次遍历，输出结果。
题目代码
#include <iostream> #include <algorithm> #include <stdio.h> using namespace std; struct node { int start;//定义每一个的开始时间 int finish;//定义每一个的结束时间 int id;//为每一个活动赋予其相应的id int section;//定义每一个活动的区间范围，也就是执行活动的时间大小 } st[1222]; int cmp(node a, node b) { if(a.finish == b.finish) { return a.section < b.section;//如果结束时间相同的话，则根据区间的大小进行排序。 } else { return a.finish < b.finish;//根据结束时间进行升序排序 } } int main() { int n; cin>>n; for(int i = 1; i <= n; i++) { cin>>st[i].start>>st[i].finish; st[i].id = i; st[i].section = st[i].finish - st[i].start; } sort(st + 1,st + n + 1,cmp);//对当前的结构体按照结束的时间进行排序，如果结束的时间相等的话，则根据区间排序。 printf("%d", st[1].id);//排序完之后，选取第一个肯定是最优的。 int x = st[1].finish; for(int i = 2; i <= n; i++) { if(st[i].start >= x) { printf(",%d", st[i].id); x = st[i].finish; } } printf("\n"); return 0; } /*************************************************** User name: jk170631黄良帅 Result: Accepted Take time: 0ms Take Memory: 200KB Submit time: 2019-11-16 17:04:54 ****************************************************/
