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

题目描述

[题目描述]

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

相关文章

来自专栏PPV课数据科学社区

【学习】《R实战》读书笔记(第一章)

第一章 R简介 本章概要 1安装R 2理解R语言 3运行R程序 本章所介绍的内容概括如下。 一个典型的数据分析步骤如图1所示。 图1:典型数据分析步骤 简而言之...

3088
来自专栏青玉伏案

Objective-C中的委托(代理)模式

        我个人更喜欢把委托(Delegate)模式称为代理(Proxy)模式。还是那句话,第一次接触代理模式是在Java中接触的,在Java中实现代理模...

1738
来自专栏数据结构与算法

2750 心系南方灾区

2750 心系南方灾区  时间限制: 1 s  空间限制: 2000 KB  题目等级 : 青铜 Bronze 题解  查看运行结果 题目描述 Descript...

3395
来自专栏葡萄城控件技术团队

ActiveReports 报表应用教程 (14)---数据可视化

葡萄城ActiveReports报表中提供了丰富的数据可视化解决方案,用户可以将数据以图像化的方式进行显示,让报表数据更加形象且便于理解。在葡萄城ActiveR...

1856
来自专栏数据分析

[数据清洗]- Pandas 清洗“脏”数据(二)

概要 了解数据 分析数据问题 清洗数据 整合代码 了解数据 在处理任何数据之前,我们的第一任务是理解数据以及数据是干什么用的。我们尝试去理解数据的列/行、记录、...

2884
来自专栏生信技能树

OMIM使用简要说明【论坛精选优秀帖】

.OMIM 为“0nline MendelianInheritance in Man”的简称,它通过对新的病症分类并命名、收录表型和相关病因基因的关系来收录人类...

31210
来自专栏大数据挖掘DT机器学习

并行爬虫和数据清洗工具(开源)

etlpy是python编写的网页数据抓取和清洗工具,核心文件etl.py不超过500行,具备如下特点 爬虫和清洗逻辑基于xml定义,不需手工编写 基于pyth...

3154
来自专栏带你撸出一手好代码

神秘的力量:信息隐藏

「信息隐藏」在软件开发领域中是一个非常重要的核心要点, 它的另一个名称叫做「封装」, 但是因为现代面向对象技术流行的原因, 「封装」似乎已被视为和private...

2677
来自专栏雨过天晴

原 安卓传感器实例

1613
来自专栏数说工作室

4. call PRXPOSN() | 撕数据!

【SAS Says·扩展篇】撕数据! | 4. call PRXPOSN() 0. 前集回顾 1. 新的问题 2. 初识 PRXPOSN() 3. 问题解决 -...

3466

扫码关注云+社区