小慕最近在负责一个游戏体验项目的试玩排期。现有 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