AlgoMooc
← 返回题库

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

中等通过率 62% · 提交 55 · 通过 34
贪心排序区间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

看不懂题目?点开图解(训练营专属)

登录后查看题目图解

题目图解为训练营学员专属内容,请先登录。

微信扫码登录还不是训练营学员?了解训练营 →
写完代码点「提交」,将对全部测试用例判题。