AlgoMooc
你已开通华为OD训练营权益,还差最后一步——完成入营激活(兑换课程 + 加飞书 + 登记服务群),即可解锁全部课程与专属服务。去激活 →
← 返回题库

N0016. 0426-最大化游戏试玩资格分发

中等通过率 64% · 提交 50 · 通过 32
贪心排序区间DPDP/贪心

小慕最近在负责一个游戏体验项目的试玩排期。现有 n 个试玩申请,每个申请都包含一个开始时间和一个结束时间。作为项目协调员,小慕需要从这些申请中选出尽可能多的试玩场次,使得: 1. 任意两场被选中的试玩时间不能重叠。 2. 允许两场试玩时间首尾相接,例如 [2,3] 和 [3,4] 可以同时被安排。 3. 目标是最大化可安排的试玩场次数量。 请问小慕最多能安排多少场试玩?

提示:带虚线的词点一下有通俗解释。

输入描述

一个长度为n (1 ≤ n ≤ 10^5) 的二维数组,内层元素是一个二元数组,其中的每个元素为两个整数 start 和 end (0 ≤ start ≤ end ≤ 10^9),表示试玩的开始和结束时间。

输出描述

一个整数,表示最多能安排的试玩数量。

示例

示例 1

输入

3
1 5
2 3
4 6

输出

2

说明:选择[2,3]和[4,6],共2位

示例 2

输入

5
1 2
3 4
5 6
7 8
9 10

输出

5

说明:5个试玩申请时间都不重合,可同时满足

示例 3

输入

1
1 5

输出

1

说明:只有一个试玩请求,可以直接安排。

示例 4

输入

3
1 5
2 4
3 6

输出

1

说明:所有试玩时间相互都冲突,只能安排一场。

时间限制 1000 ms · 内存限制 128 MB

看不懂题目?点开图解
贪心算法:按结束时间最早选择 时间 0 1 2 3 4 [1,5] [2,3] [4,6] ✓ 选中 [2,3] 和 [4,6] 先选结束最早的 [2,3],再选不冲突且结束最早的 [4,6]
写完代码点「提交」,将对全部测试用例判题。

向老师提问

针对「0426-最大化游戏试玩资格分发」把疑问、代码和报错填清楚,老师收到后能更快、更准地回复你。