给定n个活动,包括编号、开始时间、结束时间,活动都要占用一个公共资源,如教室,同一时间只有一个活动可以使用,请问同一天最多安排多少个活动?
算法思想:1.将活动按照结束时间递增排序。2.选择活动开始时间尽可能早的活动。3.活动的开始时间必须大于上个活动结束时间。
#include<iostream> #include<algorithm> using namespace std; struct Activity { int num, start, end, mark; }; bool comp(Activity a, Activity b) { return a.end < b.end; } void Select(Activity act[],int n) { int begin = act[1].start; for (int i = 1; i <= n; i++) { if(act[i].start >= begin) { begin = act[i].end; act[i].mark = 1; } } } int main() { Activity act[5]; for (int i = 1; i <= 5; i++) { cin >> act[i].start >> act[i].end; act[i].num = i; act[i].mark = 0; } sort(act + 1, act + 5, comp); Select(act, 4); for (int i = 1; i <5; i++) { if (act[i].mark == 1) { cout << act[i].num<<" " ; } } /* 参数1:第一个参数是数组的首地址,一般写上数组名就可以,因为数组名是一个指针常量。 参数2:第二个参数相对较好理解,即首地址加上数组的长度n(代表尾地址的下一地址)。 参数3:默认可以不填,如果不填sort会默认按数组升序排序。 也就是1, 2, 3, 4排序。也可以自定义一个排序函数,改排序方式为降序什么的,也就是4, 3, 2, 1这样。 */ }