[算法题] 安排会议室——贪心算法的应用-阿里云开发者社区

开发者社区> 文艺小青年> 正文

[算法题] 安排会议室——贪心算法的应用

简介:
+关注继续查看

题目描述

[题目描述]

在大公司里,会议是很多的,开会得有场子,要场子你得先在电子流里预订。
如果你是项目组新来的小弟,那么恭喜你,每天抢订会议室的任务就光荣的分给你了。
老大要求你尽可能多的订会议室,但是这些会议室之间不能有时间冲突。

[Input]
input文件中可以包括多个测试案例。
T(T ≤ 20),输入文件的第一行表示文件中有多少个测试案例。
N(1 ≤ N ≤ 500),每个测试案例的第一行表示会议室的数目。
每个测试案例中,除第一行以外表示各个会议室的信息。每行会有3个数字,分别表示会议编号、会议起始时间、会议结束时间。


[Output]
输出可以安排的最大会议数目

[I/O Example]
Input
2
6
1 1 10
2 5 6
3 13 15
4 14 17
5 8 14
6 3 12
15
1 4 8
2 2 5
3 2 6
4 4 6
5 2 3
6 1 6
7 4 7
8 3 5
9 3 8
10 1 2
11 1 7
12 2 4
13 5 6
14 4 5
15 7 8

Output
3
5

 

练习模板 

复制代码
#include <cstdio>
#include <iostream>

using namespace std;

int main(int argc, char** argv)
{
    int tc, T;
    cin >> T;
    for(tc = 0; tc < T; tc++)
    {
        //TO DO here
    }

    return 0;//Your program should return 0 on normal termination.
}
复制代码

 

代码实现

题目中要求会议时间不可以冲突,所以可以利用贪心算法,尽可能的选择会议时间结束较早的会议室,这样就能安排最多的会议室。

复制代码
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;


class MeetingRoom {
public:
    int index;
    int start;
    int end;
public:
    MeetingRoom(int i, int s, int e) : index(i), start(s), end(e) {}
};

bool isEndEarly(const MeetingRoom r1, const MeetingRoom r2) {
    return (r1.end < r2.end);
}

int main(int argc, char** argv)
{
    int tc, T;
    int num = 0;
    int count = 0;
    int index = 0;
    int start = 0;
    int end = 0;
    vector<MeetingRoom> rooms;

    freopen("input.txt""r", stdin);
    cin >> T;
    for(tc = 0; tc < T; tc++)
    {
        rooms.clear(); // clear vector

        
// get all the info of rooms
        cin >> num;
        for (int i = 0; i < num; i++) {
            cin >> index >> start >> end;
            MeetingRoom room(index, start, end);
            rooms.push_back(room);
        }

        // sort rooms for end time
        sort(rooms.begin(), rooms.end(), isEndEarly);

        // use greedy algorithm to solve promblem
        count = 1;
        MeetingRoom prev = rooms[0];
        for (vector<MeetingRoom>::iterator it = rooms.begin() + 1; it != rooms.end(); it++) {
            MeetingRoom current = *it;
            if (current.start >= prev.end) {
                count++;
                prev = current;
            }
        }

        cout << count << endl;
    }

    return 0;
}
复制代码

 本文转自静默虚空博客园博客,原文链接:http://www.cnblogs.com/jingmoxukong/p/4362211.html,如需转载请自行联系原作者

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
YOLO 人脸识别算法以及应用 (1)
第四周 特殊应用:人脸识别和神经风格转换(Special applications: Face recognition &Neural style transfer) 4.
5878 0
一致性哈希算法应用与分析
  一致性哈希算法主要使用在分布式数据存储系统中,按照一定的策略将数据尽可能均匀分布到所有的存储节点上去,使得系统具有良好的负载均衡性能和扩展性。感觉一致性哈希与数据结构中的“循环队列”还是有一点联系的。
768 0
BigData之Storm:Apache Storm的简介、深入理解、下载、案例应用之详细攻略
BigData之Storm:Apache Storm的简介、深入理解、下载、案例应用之详细攻略
25 0
ML之DR之SVD:SVD算法相关论文、算法过程、代码实现、案例应用之详细攻略
ML之DR之SVD:SVD算法相关论文、算法过程、代码实现、案例应用之详细攻略
22 0
ML之SVM:SVM算法的简介、应用、经典案例之详细攻略(一)
ML之SVM:SVM算法的简介、应用、经典案例之详细攻略
25 0
datagridview与contextmenustrip完美结合应用
上图是最佳datagridview与contextmenustrip合用效果,方法是: 而当两个以上的datagridview共同使用一个ContextMenuStrip时,【打开】【关闭】处理事件识别SourceControl的方...
811 0
3576
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载