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

题目描述

[题目描述]

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

相关文章

来自专栏章鱼的慢慢技术路

多益网络2018春季校园招聘研发岗笔试经验

2326
来自专栏牛客网

渣硕面筋release v1.0(Google已跪)

注:凡是题目需要保密的,都没有写在这里,如有同样要求请通知我修改 校招结束,我选头条 正值十一长假,赶在了小论文截稿前一天投出去了。正好国内的互联网公司校招基本...

45113
来自专栏青青天空树

2018-母牛的故事

 有一头母牛,它每年年初生一头小母牛。每头小母牛从第四个年头开始,每年年初也生一头小母牛。请编程实现在第n年的时候,共有多少头母牛?

1722
来自专栏HansBug's Lab

算法模板——Dinic最小费用最大流

实现功能:输入M,N,S,T;接下来M行输入M条弧的信息(包括起点,终点,流量,单位费用);实现功能是求出以S为源点,T为汇点的网络最大流的最小费用 其实相当的...

2806
来自专栏ACM小冰成长之路

51Nod-1618-树或非树

ACM模版 描述 ? ? 题解 这是 CFCF 上的一道原题,没有啥思路,于是找来一下题解,找到了一个远古的博客(jasonzhu8’s blog),里面有这个...

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

2199. [HZOI 2016] 活动投票

★★   输入文件:hztp.in   输出文件:hztp.out 简单对比 时间限制:0.5 s   内存限制:2 MB 【题目描述】 衡中活动很多,...

2876
来自专栏ml

HDUOJ-------2149Public Sale

Public Sale Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 ...

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

P1111 修复公路

题目背景 A地区在地震过后,连接所有村庄的公路都造成了损坏而无法通车。政府派人修复这些公路。 题目描述 给出A地区的村庄数N,和公路数M,公路是双向的。并告诉你...

2529
来自专栏Fish

CCF认证 送货

问题描述   为了增加公司收入,F公司新开设了物流业务。由于F公司在业界的良好口碑,物流业务一开通即受到了消费者的欢迎,物流业务马上遍及了城市的每条街道。然而...

1759
来自专栏前端儿

数数

我们平时数数都是喜欢从左向右数的,但是我们的小白同学最近听说德国人数数和我们有些不同,他们正好和我们相反,是从右向左数的。因此当他看到123时会说“321”。

823

扫码关注云+社区