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

题目描述

[题目描述]

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏撸码那些事

【抽象那些事】缺失抽象

16130
来自专栏take time, save time

初级程序员面试不靠谱指南(一)

    “来到这英雄宴中的人物,就算本身武功不是甚高,见识也必广博,“太祖拳法”的精要所在,可说无人不知。乔峰一招打出,人人都是情不自禁的喝了一声采!这满堂大采...

36990
来自专栏斑斓

高质量代码的特征

回想起来,我觉得我们似乎在误读Uncle Bob的Clean Code,至少我们错误地将所谓Clean与可读性代码简单地划上了等号。尤为不幸的是,在Clean ...

37950
来自专栏编程

器—术—道:程序设计教材建设经验谈

《计算机教育》2017年第11期 封面文章 引 言 程序设计的境界有3种:器—术—道。在程序设计能力培养方面,一般由“器”入门,通过熟悉“术”,最终达到“道”的...

23290
来自专栏人工智能LeadAI

讨厌算法的程序员 | 第四章 时间复杂度

增长量级 ? 函数的增长量级 上一篇算法分析基础中,我们分析了插入排序,知道了其最好情况下的运行时间为T(n) = an + b,最差情况下的运行时间为T(n...

30080
来自专栏Pythonista

面向对象的软件开发

很多人在学完了python的class机制之后,遇到一个生产中的问题,还是会懵逼,这其实太正常了,因为任何程序的开发都是先设计后编程,python的class机...

13520
来自专栏玄魂工作室

Python黑帽编程 2.0 第二章概述

于 20世纪80年代末,Guido van Rossum发明了Python,初衷据说是为了打发圣诞节的无趣,1991年首次发布,是ABC语言的继承,同时也是一...

37770
来自专栏CSDN技术头条

代码审查拯救世界?

代码审查是指阅读代码来检查源代码与编码标准的符合性以及代码质量的活动。现在,越来越多的团队倡导要进行代码审查活动,而本文作者通过一幅漫画,来诠释其对代码审查的理...

23160
来自专栏韩伟的专栏

字节的奥秘

在数码产品中,最常见的名词就是“字节”了。不管是U盘容量、手机存储空间,还是网络带宽,下载速度,都会涉及所谓“字节”这个单位。但到底“字节”是一个什么东西呢?本...

37240
来自专栏撸码那些事

【抽象那些事】缺失抽象

这是一个笑脸,那么我们是怎么知道这是一个笑脸的呢?通过抽象。人脸数以亿计,却各不相同。我们忽略了不重要的细节,如发型和发色。我们还概括了相同的东西,每个人都有两...

470150

扫码关注云+社区

领取腾讯云代金券