百度关键词热度查询工具,长春seo公司,建设网站网站名,怎样建设个人游戏网站题目描述 学校在最近几天有n个活动#xff0c;这些活动都需要使用学校的大礼堂#xff0c;在同一时间#xff0c;礼堂只能被一个活动使。由于有些活动时间上有冲突#xff0c;学校办公室人员只好让一些活动放弃使用礼堂而使用其他教室。 现在给出n个活动使用礼堂的起…题目描述 学校在最近几天有n个活动这些活动都需要使用学校的大礼堂在同一时间礼堂只能被一个活动使。由于有些活动时间上有冲突学校办公室人员只好让一些活动放弃使用礼堂而使用其他教室。 现在给出n个活动使用礼堂的起始时间bi和结束时间ei(bi ei32767)请你帮助办公室人员安排一些活动来使用礼堂要求安排的活动尽量多。
输入
第一行一个整数n(n1000) 接下来的n行每行两个整数第一个bi第二个是ei(bi ei32767)
输出
输出最多能安排的活动个数
样例输入 Copy
11
3 5
1 4
12 14
8 12
0 6
8 11
6 10
5 7
3 8
5 9
2 13样例输出 Copy
4
问题分析
我们要想想要怎么贪心我们的目标是想选到最多的活动
关键是优先选择结束时间最早的活动这样就为后续的其他活动留下更多的时间
所以我们要先根据每个活动的结束时间从小到大进行排序
第一个活动肯定先被选进来了然后我们依次看后面的活动和上一个可被选择的活动是否冲突
如果不冲突的话我们就可以选择这个活动可选择活动数1
预备知识
定义结构体其中Hd是结构体的名字你可以取自己想取的名字
其中有两个元素一个bi一个ei
struct Hd{ //这个结构体的名字叫Hdint bi; //存活动开始时间int ei; //存活动结束时间
};
cmp是一个自定义的比较函数用于确定两个Hd结构体实例在排序时的顺序为sort提供一个排序的准则
接受两个参数a和b两个参数都是对Hd结构体的引用并且是常量引用由const关键字标示所以写法是const Hd a意味着这些引用在函数内部不会修改它们指向的结构体
bool cmp(const Hd a,const Hd b) {return a.eib.ei; //按活动结束时间从小到大排序
}
每一个元素都是Hd结构体类型vector就是存多个元素的容器
所以这句话就是有n个Hd类型的元素存在名字叫a的容器当中
#include bits/stdc.h
using namespace std;struct Hd{ //这个结构体的名字叫Hdint bi; //存活动开始时间int ei; //存活动结束时间
};bool cmp(const Hd a,const Hd b) {return a.eib.ei; //按活动结束时间从小到大排序
}int main() {int n;cinn;vectorHd a(n); //这个vector存的是n个Hd类型的活动也就是每个元素是个结构体for(int i0;in;i) {cina[i].bia[i].ei; //输入每个活动的开始和结束时间}sort(a.begin(),a.end(),cmp); //对活动进行排序int ans1; //第一个活动被选择int enda[0].ei; //第一个活动的结束时间以后就是存下一个可选活动结束时间for(int i1;in;i) { //看后续的活动的情况所以下标是1开始了if(a[i].biend) { //如果当前活动的开始时间大于等于前一个可选活动结束时间ansans1; //说明该活动与前一个可选活动不冲突可选活动数加1enda[i].ei; //那么结束时间变为该可选活动结束时间}}coutans; //输出几个可安排的活动
}
