首页 > 代码库 > 【贪心算法】舞蹈室安排
【贪心算法】舞蹈室安排
Description
新活有个舞蹈室，并且只有一个舞蹈室，假设申请时间以小时为单位，每天24个小时，每周就是168小时，我们规定申请时间从每周一的0点开始递增，比如申请时间区间为【1，24】就代表周一的0点到24点，时间区间【25，48】就代表周二的0点到24点，以此类推。
现在假定你是舞蹈室的管理人员，面对一批使用舞蹈室的申请，你希望舞蹈室能尽可能给更多人使用（也就是尽可能满足更多申请数量，请注意，这里要求的并不是舞蹈室被使用的时间最多，而是被批准的申请数量最多），请你写一个程序判断这批申请里面最多能有多少个能被满足。比如有下列两个申请：
【10，12】
【11，160】
由于同一时刻舞蹈室只能给一个申请使用，所以这两个申请最多只能满足1个。
又如以下三个申请：
【10，12】
【155，168】
【11，160】
由于要求是让更多的申请能通过审批，所以我们选择的是【10，12】和【155，168】这两个区间，而不是【11，160】这个区间，所以结果是2。
Input
第一行是一个数字n，代表接下来有n个测试用例。
对于每一个测试用例，格式如下：
第一行是一个数字m，代表本周有m个申请，0 < m < 150。
接下来的m行，每行有两个数字，中间用空格隔开，代表该申请的时间区间（注意时间区间都是闭区间，且时间区间一定合法，不会超出【1，168】之外）
Output
每个测试用例输出一行，只有一个数字，代表最多能满足的申请个数。
对于这n个测试用例，输出总共有n行
Sample Input
2210 1211 160310 12155 16811 160
Sample Output
12
解题思路：
贪心算法的选择不相交区间问题。
1.用一个结构体TIME表示区间，对区间按照结束时间进行排序；
2.先结束的都可以进行安排（且不与已经安排的冲突），这样安排的活动才会尽可能多。
实现代码：
#include<iostream>using std::cout;using std::cin;using std::endl;struct TIME { int b, e;};int main() { int n, m, i, j, count; TIME T[150]; TIME tmp; cin >> n; for (; n > 0; n--) { //n个测例 cin >> m; for (j = 0; j < m; j++) { cin >> T[j].b; cin >> T[j].e; } for (j = 0; j < m - 1; j++) for (i = 0; i < m - 1 - j; i++) { if (T[i].e >= T[i + 1].e) { //按结束时间进行升序排序 tmp = T[i]; T[i] = T[i + 1]; T[i + 1] = tmp; } } for (i = 0, count = 0; i < m; i++) { if (i == 0) { count++; tmp = T[i]; continue; } if (T[i].b > tmp.e) { //下一个开始时间大于上一个安排的结束时间 tmp = T[i]; //这个活动就可以进行安排 count++; } } cout << count << endl; }}
（本博文或多或少参考过其他网上资料，但时间已久忘记当初的参考了，在此对他们表示感谢！）
【贪心算法】舞蹈室安排
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。