Problem 1374 --会场安排问题

1374: 会场安排问题

上一题 正确率: $62.45\%$ 下一题
"
Time Limit $1$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $831$ 正确数量 $519$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签 贪心 排序 数学

Description

假设要在足够多的会场里安排一批活动，并希望使用尽可能少的会场。设计一个有效的贪心算法进行安排。（这个问题实际上是著名的图着色问题。若将每一个活动作为图的一个顶点，不相容活动间用边相连。使相邻顶点着有不同颜色的最小着色数，相应于要找的最小会场数。）
算法设计：
对于给定的 k 个待安排的活动，计算使用最少会场的时间表。

Input

输入第一行有 1 个正整数 k，表示有 k 个待安排的活动。接下来的 k 行中，每行有 2 个正整数，分别表示 k 个待安排的活动开始时间和结束时间。时间以 0 点开始的分钟计。

Output

将计算出的最少会场数输出

Sample Input复制

5
1 23
12 28
25 35
27 80
36 50

Sample Output复制

3

推荐代码 查看1374 所有题解 上传题解视频得图灵币

本题记录 用 户（点击查看用户） 运行号（点击购买题解） 时 间
算法最快[$3 $ms] 骆源 949266 2023-03-26 19:45:38
内存最少[$0 $KB] Rabiit_Fz 667081 2020-11-24 14:16:31
第一AC 找队友，能刷题的那种 339157 2018-12-06 22:54:04
第一挑战 AOJ大管家 74659 2017-03-28 21:21:05

赛题来源/所属竞赛 NA 算法导论(第三版)中文完整高清版

竞赛编号 竞赛名称 竞赛时间 访问比赛
1799 2023-2024-2学期<计算机专业竞赛实训> 第3周练习：递归分治、高级排序和贪心算法【22计算机】 2024-03-11 00:00:00 请登录
1739 2022-2023-2学期<计算机专业竞赛实训> 第5周练习：递归分治、高级排序和贪心算法【21计算机12345】 2023-03-20 00:00:00 请登录
1684 2021-2022-2学期<算法分析与设计> 第5周练习：贪心算法 2022-03-21 08:00:00 请登录
1611 2020-2021-2学期<算法分析与设计> 第9周练习：贪心算法 2021-04-12 08:00:00 请登录
1196 2018NOIP冲刺班国庆班训练赛（第二场）提高组 2018-10-03 09:30:00 请登录